计算一组数字的所有子集

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, 53, 55我认为问题出在零件list.removeAll（list）;中。但我不知道如何纠正它。

Answer 1

您想要的就是Powerset。这是一个简单的实现：

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}：

移除{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++){

    ArrayList<Integer> subset = new ArrayList<Integer>();

    for(int j = 0; j < n; j++){

        if((i>>j) & 1) == 1){ // bit j is on

            subset.add(numbers.get(j));

        }

    }

    // print subset

}