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