计算一组数字的所有子集

algorithm java subset

2022-09-01 01:42:04

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

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

你想要的叫做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}{2, 3};
- 删除，并执行的电源集{2}{3};
  - 删除，并执行的电源集{3}{};
    - 的幂集是{}{{}};
  - 的功率集与{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} }

答案 2

只是一个如何解决问题的入门书：

方法 1

获取号码列表的第一个元素
从剩余的数字列表中生成所有子集（即没有所选数字列表的数字列表）=>递归！
对于在上一步中找到的每个子集，将子集本身以及与步骤 1 中选择的元素联接的子集添加到输出中。

当然，您必须检查基本情况，即您的号码列表是否为空。

方法 2

众所周知，具有元素的集合具有子集。因此，您可以按二进制从到进行计数，并将二进制数解释为相应的子集。请注意，此方法需要一个具有足够数字的二进制数来表示整个集合。n2^n02^n

将两种方法之一转换为代码应该是一个不太大的问题。