Leetcode t39: combined sum

Title Description

To give you one No repeating elements Array of integers for candidates And a target integer target , find candidates You can make the sum of numbers as the target number target Of all Different combinations , And return... As a list . You can press In any order Return these combinations .

candidates Medium The same Numbers can Unlimited repeat selected . If the selected number of at least one number is different , Then the two combinations are different .

For a given input , Guarantee and for target The number of different combinations of is less than 150 individual .

Example 1：

Input ：candidates = [2,3,6,7], target = 7
Output ：[[2,2,3],[7]]
explain ：
2 and 3 Can form a set of candidates ,2 + 2 + 3 = 7 . Be careful 2 You can use it multiple times .
7 Is also a candidate , 7 = 7 .
Only these two combinations .

Example 2：

Input : candidates = [2,3,5], target = 8
Output : [[2,2,2,2],[2,3,3],[3,5]]

Example 3：

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

Ideas

Very conventional dfs topic , But I haven't played for a long time dfs Code. , Make a note of .

Code

	List<List<Integer>> res = new ArrayList<List<Integer>>();
	int n, tar;
	int[] nums;
	
	//  Currently selected combination , Select the number , The present and 
	void dfs(List<Integer> lis, int cur,  int s) {
    
		if(cur == n) {
    
			if(s == tar)
				res.add(lis);
		} else {
    
// for(int x: lis) System.out.print(x+"\t"); System.out.println("\t,"+cur+"-"+s);
			// Optional for the current number , Optional 
			//  choose , See if it exceeds , prune 
			if(s + nums[cur] <= tar) {
    
				List<Integer> tmp = new ArrayList<Integer>(lis);
				tmp.add(nums[cur]);
				dfs(tmp, cur, s + nums[cur]);
			}
			//  No election 
			if(true) {
    
				List<Integer> tmp = new ArrayList<Integer>(lis);
				dfs(tmp, cur+1, s);
			}
		}
	}
	
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
    
    	nums = candidates;
        n = candidates.length;
        tar = target;
        dfs(new ArrayList<Integer>(), 0, 0);
    	return res;
    }