# Combination Sum II    ## Intuition

This is almost the same as problem 39. Combination Sum. The only difference is that one number can only be used once.

So we could do a DFS to find the target number. During the DFS process, we should keep the path. And once we get an zero, we copy the current path and add it to the result.

To avoid duplicate, we only search for children which is greater than current node.

And note that, for candidates like [1, 1, 2, 5], we don't need to gothrough the path where second "1" is the first value. Because the result is the same as where the first "1" is in the first position.

## Solution

``````
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
self.ans = []
path = []
self._helper(target, 0, candidates, path)
return self.ans

def _helper(self, target, start, candidates, path):
if target == 0:
self.ans.append(path[:])
return
elif target < 0:
return

prev = None
for i in range(start, len(candidates)):
if candidates[i] == prev:
continue
prev = candidates[i]
path.append(candidates[i])
self._helper(target - candidates[i], i + 1, candidates, path)
path.pop()

``````