题意：给定一个数组和一个target值，返回和为target且为给定数组子数组的所有结果，和上一题不同的是有重复元素
思路：深度优先搜索遍历每一种可能结果，思路和39题类似，唯一不同的是注意去除重复
思想：DFS
复杂度：时间O(n2)，空间O(n^2)
class Solution {
List<List<Integer>> res = new ArrayList();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
int len = candidates.length;
if(len == 0)
return res;
Arrays.sort(candidates);
build(candidates, target, new ArrayList<Integer>(), 0, 0);
return res;
}
void build(int[] a, int target, List<Integer> temp, int index, int sum) {
if(sum > target)
return;
if(sum == target) {
res.add(new ArrayList(temp));
return;
}
for(int i=index;i<a.length;i++) {
// 去除重复的元素，
if(i>index && a[i] == a[i-1])
continue;
temp.add(a[i]);
build(a, target, temp, i+1, sum + a[i]);
temp.remove(temp.size() - 1);
}
}
}
