Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]

Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

 

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<Integer> ans = new ArrayList<Integer>();
        Arrays.sort(candidates);
        backTrack(candidates, target, 0, ans, 0);
        return result;
    }
    
    public void backTrack(int[] candidates, int target, int start, List<Integer> ans, int sum){
        if(start >= candidates.length || sum + candidates[start] > target) 
            return; //not found
        else if(sum + candidates[start] == target ){ //found an answer
            List<Integer> new_ans = new ArrayList<Integer>(ans); //不能用List<Integer> new_ans = ans;这个只是创建了原List的一个引用
            new_ans.add(candidates[start]);
            result.add(new_ans);
        }
        else{
            // not choose current candidate
            backTrack(candidates,target,start+1,ans,sum);
                
            //choose current candidate
            ans.add(candidates[start]);
            backTrack(candidates,target,start,ans,sum+candidates[start]);
            ans.remove(ans.size()-1); //List是按引用传递，为了不影响递归，需要复原
        }
    }
    
    private List<List<Integer>> result = new ArrayList<List<Integer>>();
}

注意List按引用（地址）传递，需要新new一个，或是复原，以不影响其他部分

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄