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

Each number in candidates may only be used once in the combination.

Note:


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


Example 1:


Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]


Example 2:


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

Difficulty: interview

Starter code:

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        

Solutions:
class Solution:
     def combinationSum2(self, candidates, target):
                 
         def dfs(i, val, path):
             while i < len(candidates):
                 num = candidates[i]
                 val_ = val + num
                 path_ = path + [num]
                 if val_ > target:
                     return
                 elif val_ == target:
                     ans.append(path_)
                     return                  
                 dfs(i+1, val_, path_)
                 while i<len(candidates)-1 and candidates[i]==candidates[i+1]:
                     i += 1
                 i += 1
                
         candidates = sorted(candidates)
         ans = []
         dfs(0, 0, [])
         return ans


 class Solution:
     def combinationSum2(self, candidates, target):
         """
         :type candidates: List[int]
         :type target: int
         :rtype: List[List[int]]
         """
         if len(candidates)==0:
             return []
 
 
         candidates = sorted(candidates)
         print(candidates)
 
         results = []
 
 
         def find(curr_comb, curr_sum, candidates): #靠副作用填充results
             #curr_comb = curr_comb[:]
             for i,cand in enumerate(candidates):
 
                 if (cand+curr_sum) < target:
                     new_curr_comb = curr_comb[:]
                     new_curr_comb.append(cand)
                     find(new_curr_comb, curr_sum+cand, candidates[i+1:])
                 elif (cand+curr_sum) == target:
                     new_curr_comb = curr_comb[:]
                     new_curr_comb.append(cand)
                     if new_curr_comb not in results:
                         results.append(new_curr_comb)
                     #print(curr_comb, curr_sum, cand, 'target:',target)
                 else:
                     break
 
 
         find([], 0, candidates)
 
         return results

class Solution:
     def combinationSum2(self, candidates, target):
         """
         :type candidates: List[int]
         :type target: int
         :rtype: List[List[int]]
         """
         if not candidates:
             return []
         result = []
         candidates.sort()
         self.dfs(result, [], 0, target, candidates)
         return result
     
     def dfs(self, result, combin, start, target, candidates):
         if target == 0:
             result.append([i for i in combin])
         else:
             for index in range(start, len(candidates)):
                 if candidates[index] > target:
                     break
                 if (index > start and candidates[index] == candidates[index - 1]):
                     continue
                 combin.append(candidates[index])
                 self.dfs(result, combin, index + 1, target - candidates[index], candidates)
                 combin.pop()


class Solution:
     def combinationSum2(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: List[List[int]]
         """
         def dfs(a, i, target):
             for j in range(i, len(nums)):
                 if target <= nums[j]:
                     if target == nums[j]:
                         ans.append(a+[nums[j]])
                     break
                 if i == j or nums[j] != nums[j-1]:
                     dfs(a+[nums[j]], j+1, target-nums[j])
 
         ans = []
         nums.sort()
         dfs([], 0, target)
         return ans


class Solution:
     def combinationSum2(self, candidates, target):
         """
         :type candidates: List[int]
         :type target: int
         :rtype: List[List[int]]
         """
         def helper(L, target, path, ans):
             if target == 0:
                 ans.append(path)
                 return
             for i in range(len(L)):
                 if L[i] > target:
                     return
                 if i > 0 and L[i] == L[i-1]:
                     continue
                 helper(L[i+1:], target-L[i], path+[L[i]], ans)
         
         ans = []
         helper(sorted(candidates), target, [], ans)
         return ans

class Solution:
     def combinationSum2(self, candidates, target):
         """
         :type candidates: List[int]
         :type target: int
         :rtype: List[List[int]]
         """
         res = []
         candidates.sort()
         self.dfs(candidates,target,0,[],res)
         return res
 #60%
     
     def dfs(self,nums,target,index,path,res):
         if target<0:
             return 
         if target == 0:
             res.append(path)
             return 
         for i in range(index,len(nums)):
             if i>index and nums[i] == nums[i-1]:
                 continue
             if nums[i] > target:    #   提升到93%
                 break
             self.dfs(nums,target-nums[i],i+1,path+[nums[i]],res)

class Solution:
     def combinationSum2(self, candidates, target):
         """
         :type candidates: List[int]
         :type target: int
         :rtype: List[List[int]]
         """
         result=[]
         def combinationSumRecu(self,candidates,target,start,intermediate,result):
             if target==0:
                 result.append(list(intermediate))
             while start<len(candidates) and candidates[start]<=target:
                 intermediate.append(candidates[start])
                 combinationSumRecu(self,candidates,target-candidates[start],start+1,intermediate,result)
                 start+=1
                 intermediate.pop()
                 while start>0 and start<len(candidates) and candidates[start]==candidates[start-1]:
                     start+=1
                     
                 
         
         combinationSumRecu(self,sorted(candidates),target,0,[],result)
         return result

class Solution:
     def combinationSum2(self, candidates, target):
         """
         :type candidates: List[int]
         :type target: int
         :rtype: List[List[int]]
         """
         dp = [None] + [set() for i in range(target)]
         candidates.sort()
         for i in candidates:
             if i > target:
                 break
             for j in range(target-i,0,-1):
                 dp[i+j] |= {_ + (i,) for _ in dp[j]}
             dp[i].add((i,))
         return list(dp[-1])

class Solution:
     def find(self,candidates,result,current,target,pos,num,current_num):
         if target==0:
             temp = current[:]
             result.append(temp)
         else:
             for i in range(pos,len(candidates)):
                 n = str(candidates[i])
                 if candidates[i]>target or num[n]<current_num[n]:
                     break
                 if num[n]==current_num[n]:
                     continue
                 current.append(candidates[i])
                 current_num[n] +=1
                 self.find(candidates,result,current,target-candidates[i],i,num,current_num)
                 value = current.pop()
                 current_num[str(value)] -=1
 
     def combinationSum2(self,candidates, target):
         result = []
         current =[]
         candidates.sort()
         can = candidates[:]
         count = 0;
         num = {}
         current_num={}
         for i in range(len(candidates)):
             if i==0 or candidates[i]!=candidates[i-1]:
                 num[str(candidates[i])]=1
                 current_num[str(candidates[i])]=0
                 continue
             else:
                 num[str(candidates[i])]+=1
                 del can[i-count]
                 count +=1
         self.find(can,result,current,target,0,num,current_num)
         return result


class Solution:
     def combinationSum2(self, candidates, target):
         """
         :type candidates: List[int]
         :type target: int
         :rtype: List[List[int]]
         """
         def produce(nums, target, current, output):
             if target == 0:
                 output.append(list(current))
                 return
             for i, n in enumerate(nums):
                 if n > target: continue
                 # avoid duplicate solutions
                 if i > 0 and nums[i] == nums[i-1]: continue
                 current.append(n)
                 # each num can be used only once: nums[i+1:]
                 produce(nums[i+1:], target - n, current, output)
                 current.pop()
 
         output = []
         candidates.sort()
         produce(candidates, target, [], output)
         return output

class Solution:
     def combinationSum2(self, candidates, target):
         """
         :type candidates: List[int]
         :type target: int
         :rtype: List[List[int]]
         """
         sortedCandidates = sorted(candidates)
         if len(candidates) == 0 or target < sortedCandidates[0]:
             return []
         if target == sortedCandidates[0]:
             return [[sortedCandidates[0]]]
         resultWith0 = self.combinationSum2(sortedCandidates[1:], target - sortedCandidates[0])
         nextIndex = 0
         while nextIndex < len(candidates) and sortedCandidates[nextIndex] == sortedCandidates[0]:
             nextIndex += 1
         
         resultNo0 = self.combinationSum2(sortedCandidates[nextIndex:], target)
         
         return [[sortedCandidates[0]] + item for item in resultWith0] + resultNo0

class Solution:
     def combinationSum2(self, candidates, target):
         """
         :type candidates: List[int]
         :type target: int
         :rtype: List[List[int]]
         """
         def backtracing(nums,target,idx,path,ret):
             if not target :
                 if path not in ret :
                     ret.append(path)
             for i in range (idx,len(nums)):
                 if nums[i] > target :
                     break
                 backtracing(nums,target-nums[i],i+1,path+[nums[i]],ret)
         candidates.sort()
         ret = []
         backtracing(candidates,target,0,[],ret)
         return ret

class Solution:
     def combinationSum2(self, candidates, target):
         """
         :type candidates: List[int]
         :type target: int
         :rtype: List[List[int]]
         """
         def combination(candidates, k, target, res, result):
             for i in range(k,len(candidates)):
                 if target == candidates[i]:
                     temp = [j for j in res]
                     temp.append(candidates[i])
                     temp.sort()
                     if temp not in result:
                         result.append(temp)
                     return
                 elif target < candidates[i]:
                     return
                 else:
                     res.append(candidates[i])
                     combination(candidates, i+1, target - candidates[i], res, result)
                     res.pop()
 
         candidates.sort()
         res = []
         result = []
         combination(candidates, 0, target, res, result)
         return(result)

class Solution(object):
     def combinationSum2(self, candidates, target):
         """
         :type candidates: List[int]
         :type target: int
         :rtype: List[List[int]]
         """
         result = []
         temp = []
         candidates.sort(reverse=True)
 
         self.util(candidates, target, result, temp)
         return result       
 
     def util(self, nums, target, result, temp):
 
         for i in range(len(nums)): 
             if nums[i] == target and (temp + [nums[i]] not in result):
                 result.append(temp + [nums[i]])
             elif nums[i] < target:
                 self.util(nums[i + 1:], target - nums[i], result, temp + [nums[i]])
 
         return