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.

It is very similar to combination sum I. But we have duplicate numbers here.

# Duplicates numbers are allowed.

# Modify from comb sum I

In the recursive call, we call

```
def dfs(self, nums, index, target, path):
if target < 0:
return
if target == 0:
self.all_path.append(path)
for i in range(index, len(nums)):
self.dfs(nums, i + 1, target - nums[i], path + [nums[i]])
```

The index is i + 1. That means later recursive call to dfs can only use numbers from index from i + 1 to end.

This makes sure each number is used only once. But can’t avoid duplicate.

EG: Input: candidates = [10,1,2,7,6,1,5], target = 8,

Our algorithm will return two [1,7].

One is the produced by first calling dfs(nums, 1, 7, [1]) then dfs(nums, 3, 0, [1,7]).

The other [1,7] is from dfs(nums, 3, 1, [7]), then dfs(nums, 5, 0, [7, 1]).

# Root of the problem

The problem is because we used the same number at the same level. (Assume we sort the candidates first).

EG: Input: candidates = [1,1,7], target = 8,

At the same level of the tree, our previous algorithm will add two paths that starts with 1 to the solution by calling dfs(nums, 1, 7, [1]) and dfs(nums, 2, 7, [1]). This will generate duplicate.

# Avoid the problem

## Use a dict

We use a dictionary to record the numbers used at each level. And we only recurse when the number is not seen at that level.

## Use pre and cur

since the input is sorted. We can just recurse when the previous num[i] is different from current nums[i]

```
def combinationSum2(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
candidates.sort()
self.dfs(candidates, 0, target, [])
return self.all_path
def dfs(self, nums, index, target, path):
if target < 0:
return
if target == 0:
self.all_path.append(path)
prev = None
for i in range(index, len(nums)):
cur = nums[i]
if prev != cur:
self.dfs(nums, i + 1, target - nums[i], path + [nums[i]])
prev = cur
```