Combination Sum II

Problem Id: 40 Difficulty: Medium Tag: Array Tag: Backtracking


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()