我想找到一组整数的子集。这是具有回溯功能的“子集总和”算法的第一步。我已经编写了以下代码,但是没有返回正确的答案:
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);中。但我不知道如何纠正它。
您想要的就是 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}
{1}
{2, 3}
{2}
{3}
{}
{{}}
3
{ {}, {3} }
{ {}, {3}, {2}, {2, 3} }
{ {}, {3}, {2}, {2, 3}, {1}, {3, 1}, {2, 1}, {2, 3, 1} }