## Description

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]
]


## Solutions

### 1. Backtracking

# Time: O(n^target)
# Space: O(n)
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
res = []
candidates.sort()
self.dfs(candidates, 0, [], target, res)
return res

def dfs(self, candidates, start, path, target, res):
if target == 0:
res.append(path)
n = len(candidates)
for i in range(start, n):
if i > start and candidates[i] == candidates[i-1]:
continue
if target >= candidates[i]:
self.dfs(candidates, i + 1, path + [candidates[i]], target - candidates[i], res)
# 172/172 cases passed (68 ms)
# Your runtime beats 67.83 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.9 MB)


### 2. 迭代解法

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

ans = [[] for i in range(target + 1)]
ans[0] = [[]]
candidates = sorted(candidates)

for i in candidates:
for j in range(target, -1, -1):
if i <= j:
for p in ans[j - i]:
if p + [i] not in ans[j]:
ans[j].append(p + [i])

return ans[target]