一尘不染

计算一组数字的所有子集

algorithm

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

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);中。但我不知道如何纠正它。


阅读 313

收藏
2020-07-28

共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} }
2020-07-28