我想找到一个整数集的子集。它是萨姆亚群的算法与回溯的第一步。我写了下面的code,但它并没有返回正确的答案:
I want to find the subsets of a set of integers. it is the first step of "Sum of Subsets" algorithm with backtracking. I have written the following code, but it doesn't return the correct answer:
code:
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;
}
例如,如果我想计算集合的子集= {1,3,5} 我的方法的结果是:
for example if I want to calculate the subsets of set = {1, 3, 5} The result of my method is :
1, 3, 5, ********************
5, ********************
3, 5, ********************
5, ********************
3, 5, ********************
5, ********************
我希望它产生
I want it to produce
1, 3, 5
1, 5
3, 5
5
我认为这个问题是从零件 list.removeAll(名单); 但我不知道如何纠正它。
I think the problem is from the part list.removeAll(list); but I dont know how to correct it.
你想要什么叫做 Powerset的 。下面是一个简单的实现它:
What you want is called a Powerset. Here is a simple implementation of it:
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}
,并执行幂为 {}
;
的Powerset的{}
是 {{}}
;
Remove {1}
, and execute powerset for {2, 3}
;
Remove {2}
, and execute powerset for {3}
;
Remove {3}
, and execute powerset for {}
;
Powerset of {}
is {{}}
;