题意：给定一个数组和一个target值，返回和为target且为给定数组子数组的所有结果
思路：深度优先搜索遍历每一种可能结果，具体解析见代码注释
思想：DFS
复杂度：时间O(n2)，空间O(n^2)
class Solution {
// 结果数组
List<List<Integer>> res = new ArrayList();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
int len = candidates.length;
// 数组为空直接返回结果
if(len == 0)
return res;
build(candidates, target, 0, 0, new ArrayList<Integer>());
return res;
}
// dfs
// a是给定数组
// target是目标和
// index是每次递归开始的数组节点，用来去重复结果，比如[2,3,2], [2,2,3]就是重复结果
// sum当前子数组的和
// temp当前子数组
void build(int[] a, int target, int index, int sum, List<Integer> temp) {
// 当前子数组的和大于目标和返回
if(sum > target)
return;
// 当前子数组的和等于目标和，加入结果并返回
if(sum == target) {
res.add(new ArrayList(temp));
return;
}
// 对index到数组结尾的每一个元素进行dfs
for(int i=index;i<a.length;i++) {
temp.add(a[i]);
build(a, target, i, sum + a[i], temp);
temp.remove(temp.size()-1);
}
}
}
