计算一组数字的所有子集

Question

我想找到一组整数的子集。这是具有回溯功能的“子集总和”算法的第一步。我已经编写了以下代码，但是没有返回正确的答案：

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}的子集，则我的方法的结果是：

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

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

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

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

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

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

我希望它产生：

1, 3, 5 

1, 5

3, 5

5

我认为问题出在零件list.removeAll（list）;中。但我不知道如何纠正它。

Answer 1

您想要的就是Powerset。这是一个简单的实现：public static Set<Set<Integer>> powerSet(Set<Integer> originalSet) {&nbsp; &nbsp; &nbsp; &nbsp; Set<Set<Integer>> sets = new HashSet<Set<Integer>>();&nbsp; &nbsp; &nbsp; &nbsp; if (originalSet.isEmpty()) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sets.add(new HashSet<Integer>());&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return sets;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; List<Integer> list = new ArrayList<Integer>(originalSet);&nbsp; &nbsp; &nbsp; &nbsp; Integer head = list.get(0);&nbsp; &nbsp; &nbsp; &nbsp; Set<Integer> rest = new HashSet<Integer>(list.subList(1, list.size()));&nbsp; &nbsp; &nbsp; &nbsp; for (Set<Integer> set : powerSet(rest)) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Set<Integer> newSet = new HashSet<Integer>();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; newSet.add(head);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; newSet.addAll(set);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sets.add(newSet);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sets.add(set);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return sets;&nbsp; &nbsp; }我将为您提供一个示例，以说明该算法如何用于的幂集{1, 2, 3}：移除{1}并执行powerset {2, 3};移除{2}并执行powerset {3};移除{3}并执行powerset {};的幂集{}为{{}};的幂{3}被3联合{{}}= { {}, {3} };的幂{2, 3}被{2}联合{ {}, {3} }= { {}, {3}, {2}, {2, 3} };的幂{1, 2, 3}被{1}联合{ {}, {3}, {2}, {2, 3} }= { {}, {3}, {2}, {2, 3}, {1}, {3, 1}, {2, 1}, {2, 3, 1} }。

Answer 2

就在底漆你怎么能解决这个问题：方法1将号码列表中的第一个元素从剩余的号码列表（即没有选定号码列表的号码列表）生成所有子集=>递归！对于上一步中找到的每个子集，将子集本身以及与在步骤1中选择的元素连接的子集添加到输出中。当然，您必须检查基本情况，即您的号码列表是否为空。方法2众所周知，带有n元素的集合具有2^n子集。因此，您可以算出从0到2^n的二进制数，并将二进制数解释为相应的子集。请注意，此方法需要一个二进制数，该二进制数必须具有足够的数字来表示整个集合。将两种方法之一转换为代码应该不是一个太大的问题。

Answer 3

您的代码确实令人困惑，没有解释。您可以使用位掩码进行迭代操作，该位掩码确定集合中的数字。从0到2 ^ n的每个数字都以其二进制表示形式给出一个唯一的子集，例如对于n = 3：i = 5-> 101以二进制形式，选择第一个和最后一个元素i = 7-> 111以二进制形式，选择前3个元素假设有n个元素（n <64，如果n大于64，则将永远运行该元素）。for(long i = 0; i < (1<<n); i++){&nbsp; &nbsp; ArrayList<Integer> subset = new ArrayList<Integer>();&nbsp; &nbsp; for(int j = 0; j < n; j++){&nbsp; &nbsp; &nbsp; &nbsp; if((i>>j) & 1) == 1){ // bit j is on&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; subset.add(numbers.get(j));&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; // print subset}