Leetcode t40: combined sum II

Title Description

Given a set of candidate numbers candidates And a target number target , find candidates All can make numbers and target The combination of .

candidates Each number in can only be used in each combination once .

Be careful ： A solution set cannot contain duplicate combinations .

Example 1:

Input : candidates = [10,1,2,7,6,1,5], target = 8,
Output :
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

Example 2:

Input : candidates = [2,5,2,1,2], target = 5,
Output :
[
[1,2,2],
[5]
]

Tips

1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

Ideas

And the last question ： Combinatorial summation I equally , Is to use dfs, however , If you still use the idea of the previous question , Despite the pruning , Still timeout . Here is another dfs Ideas .
Because each candidate[i] It's all in the range of [0, 50], So you can define an array to record the number of each element , Then proceed according to this array dfs Search for .

Code

	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];
	
	//  Currently selected combination , Select the number , The present and ,  The rest and 
	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 {
    
				// For the current number 
				// choose , See if it exceeds , prune 
				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);
					}
				}
				
				//  No election , If the rest is still not enough , Then prune 
				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;
    }