40. Combination Sum II
## 思路
要列出组合就用backtracking
每个candidate只能用一次 但可能会有重复的num
所以必须要考虑重复的arr
e.g. [2,1,2,2] target: 5
[[1,2,2]] # 1+任取两个2
-> 先做排序, 然后在backtracking的过程中skip掉重复的num
## Code
```python
class Solution:
def combinationSum2(self, candidates: List[int], target: int) ->
List[List[int]]:
candidates.sort()
n = len(candidates)
ans = []
arr = []
def backtrack(i, curr_sum):
if curr_sum == target:
ans.append(arr[:])
return
if i == n or curr_sum > target:
return
for j in range(i, n):
# skip duplicate
if j > i and candidates[j] == candidates[j-1]:
continue
if candidates[j] + curr_sum > target:
break
arr.append(candidates[j])
backtrack(j+1, curr_sum + candidates[j])
arr.pop()
backtrack(0, 0)
return ans
```