题目描述
给定候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 每个组合中的每个数字只能使用 一次 。
注：解集不能包含重复组合。
示例 1:
输入: candidates = [10，1，2，7，6，1，5] target = 8, 输出: [ [1,1,6], [1,2,5], [1,7], [2,6] ]
示例 2:
输入: candidates = [2，5，2，1，2]， target = 5, 输出: [ [1,2,2], [5] ]
提示
1 <= candidates.length <= 100 1 <= candidates[i] <= 50 1 <= target <= 30
思路
和上一个问题一样，组合总和I一样使用dfs，但是，如果仍采用上一题的思路，尽管进行了剪枝，仍会超时。这里采用另一种dfs思路。 由于每个candidate[i][0， 因此，可以定义一个数组来记录每个元素的数量，然后根据这个数组dfs搜索。
代码
List<List<Integer>> res = new ArrayList<List<Integer>>(); HashMap<List<Integer>, Integer> map = new HashMap<List<Integer>, Integer>(); int tar; int[] nums = new int[51]; // 当前选择的组合选择了当前和， 剩下和 void dfs(List<Integer> lis, int cur, int s, int ts) {
if(cur == 51) {
if(s == tar && map.getOrDefault(lis, -1)==-1) {
map.put(lis, 1);
}
} else {
// for(int x: lis) System.out.print(x+","); System.out.println("\t"+cur+","+s);
if(nums[cur] == 0) dfs(lis, cur+1, s, ts);
else {
//对于当前数字
//选，看是否超过，剪枝
List<Integer> tmp = new ArrayList<Integer>(lis);
for(int i = 1; i <= nums[cur]; i++) {
if(s + i*cur <= tar) {
tmp.add(cur);
dfs(tmp, cur+1, s + i*cur, ts-i*cur);
}
}
// 不选，如果剩下的都装仍不能满足，则剪枝
if(s+ts-cur >= tar) {
List<Integer> tmp2 = new ArrayList<Integer>(lis);
dfs(tmp2, cur+1, s, ts-cur);
}
}
}
}
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
tar = target;
for(int x: candidates) nums[x]++;
int s = 0;
for(int x: candidates) s += x;
dfs(new ArrayList<Integer>(), 0, 0, s);
for(List<Integer> lis: map.keySet()) {
res.add(lis);
}
return res;
}