import java.util.ArrayList;
/**
* 子集和问题
*/
public class Subset {
ArrayList list = new ArrayList(); //用于存放求取子集中的元素
ArrayList<ArrayList> resultList = new ArrayList<ArrayList>(); //用于存放满足条件的集合
/*
* 参数step：选中数组A中第step个元素为子集元素
* 函数功能：求取数组A中一个子集元素，其相加之和等于m
*/
public void getSubSet(int[] arr, int sum, int step) {
while(step < arr.length) {
list.add(arr[step]); //递归执行语句，向数组链表中添加一个元素
int s = 0;
for (int i = 0;i < list.size();i++) {
s += (int)list.get(i);
}
if(s == sum) { //链表中元素和等于m
System.out.println(list);
resultList.add(list);
}
step++;
getSubSet(arr, sum, step);
list.remove(list.size() - 1); //回溯执行语句，删除数组链表最后一个元素
}
}
public static void main(String[] args) {
Subset test = new Subset();
int[] arr = new int[6];
for(int i = 0;i < 6;i++) {
arr[i] = i + 1;
}
test.getSubSet(arr, 8, 0);
System.out.println("-----------------------------------------");
for (ArrayList a:test.resultList) {
System.out.println(a);
}
}
}
输出的结果是：
[1, 2, 5]
[1, 3, 4]
[2, 6]
[3, 5]
-----------------------------------------
[]
[]
[]
[]
Process finished with exit code 0