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.
Note:
target) will be positive integers.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]
]
注意需要排序
1 class Solution { 2 private List<List<Integer>> res = new ArrayList<>(); 3 public List<List<Integer>> combinationSum2(int[] candidates, int target) { 4 List<Integer> temp = new ArrayList<Integer>(); 5 Arrays.sort(candidates); 6 help(temp,candidates,0,0,target); 7 return res; 8 } 9 private void help(List<Integer> temp,int[] nums,int index,int cursum,int target){ 10 if(cursum>target) 11 return; 12 else if(cursum==target) 13 res.add(new ArrayList<Integer>(temp)); 14 else{ 15 for(int i = index;i<nums.length;i++){ 16 if(i > index && nums[i] == nums[i-1]) continue; // skip duplicates 17 temp.add(nums[i]); 18 help(temp,nums,i+1,cursum+nums[i],target); 19 temp.remove(temp.size()-1); 20 } 21 } 22 } 23 }
1 class Solution: 2 def __init__(self): 3 self.res = [] 4 def combinationSum2(self, candidates, target): 5 """ 6 :type candidates: List[int] 7 :type target: int 8 :rtype: List[List[int]] 9 """ 10 def help(x,temp,index,cursum,t): 11 temp = temp[:] 12 if cursum>t: 13 return 14 if(cursum==t): 15 self.res.append(temp) 16 for i in range(index,len(x)): 17 if(i > index and x[i]==x[i-1]): 18 continue 19 temp.append(x[i]) 20 help(x,temp,i+1,cursum +x[i],t) 21 temp.pop(-1) 22 23 24 x = sorted(candidates) 25 help(x,[],0,0,target) 26 return self.res 27 28
原文：https://www.cnblogs.com/zle1992/p/8902499.html