计算一组数字的所有子集 [英] Calculating all of the subsets of a set of numbers

问题描述

我想找到一组整数的子集.这是带有回溯的子集总和"算法的第一步.我编写了以下代码，但没有返回正确答案:

I want to find the subsets of a set of integers. It is the first step of "Sum of Subsets" algorithm with backtracking. I have written the following code, but it doesn't return the correct answer:

BTSum(0, nums);
///**************
ArrayList<Integer> list = new ArrayList<Integer>();

public static ArrayList<Integer> BTSum(int n, ArrayList<Integer> numbers) {
    if (n == numbers.size()) {
        for (Integer integer : list) {
            System.out.print(integer+", ");
        }
        System.out.println("********************");
        list.removeAll(list);
        System.out.println();
    } else {
        for (int i = n; i < numbers.size(); i++) {
            if (i == numbers.size() - 1) {
                list.add(numbers.get(i));
                BTSum(i + 1, numbers);
            } else {
                list.add(numbers.get(i));
                for (int j = i+1; j < numbers.size(); j++)
                BTSum(j, numbers);
            }
        }
    }

    return null;
}

比如我想计算set = {1, 3, 5}的子集我的方法的结果是:

For example, if I want to calculate the subsets of set = {1, 3, 5} The result of my method is:

 1, 3, 5, ********************

 5, ********************

 3, 5, ********************

 5, ********************

 3, 5, ********************

 5, ********************

我希望它产生:

1, 3, 5 
1, 5
3, 5
5

我认为问题出在部分list.removeAll(list);但我不知道如何纠正它.

I think the problem is from the part list.removeAll(list); but I dont know how to correct it.

推荐答案

你想要的是电源.这是它的一个简单实现:

What you want is called a Powerset. Here is a simple implementation of it:

public static Set<Set<Integer>> powerSet(Set<Integer> originalSet) {
        Set<Set<Integer>> sets = new HashSet<Set<Integer>>();
        if (originalSet.isEmpty()) {
            sets.add(new HashSet<Integer>());
            return sets;
        }
        List<Integer> list = new ArrayList<Integer>(originalSet);
        Integer head = list.get(0);
        Set<Integer> rest = new HashSet<Integer>(list.subList(1, list.size()));
        for (Set<Integer> set : powerSet(rest)) {
            Set<Integer> newSet = new HashSet<Integer>();
            newSet.add(head);
            newSet.addAll(set);
            sets.add(newSet);
            sets.add(set);
        }
        return sets;
    }

我给你一个例子来解释算法如何在{1, 2, 3}的幂集上工作:

I will give you an example to explain how the algorithm works for the powerset of {1, 2, 3}:

• 去掉{1}，对{2, 3}执行powerset；
  • 去掉{2}，对{3}执行powerset；
    • 移除{3}，并为{}执行powerset；
      • {} 的 Powerset 为 {{}};
      • Remove {1}, and execute powerset for {2, 3};
        • Remove {2}, and execute powerset for {3};
          • Remove {3}, and execute powerset for {};
            • Powerset of {} is {{}};

            这篇关于计算一组数字的所有子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！