Leetcode T40: 组合总和II

题目描述

给定一个候选人编号的集合 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, 50]，所以可以定义一个数组记录每个元素的个数，然后根据这个数组进行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;
    }