40. Combination Sum II

# Medium

Very similar to #39, the only difference is to keep avoid dupplicate combinations. Then should think how to filter the dupplication.

Solution: sort the candidates list, then avoid repeating to use same element in list.

if i > x and s[i] == s[i-1]:
                continue

Python

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        sub = []
        candidates.sort()
        self.helper(candidates, sub, target, 0, result)
        return result
    
    def helper(self, s, sub, target, x, result):
        if target == 0:
            result.append(sub[:])
            return
        elif target < 0:
            return 
        
        for i in range(x, len(s)):
            if i > x and s[i] == s[i-1]:
                continue
            sub.append(s[i])
            self.helper(s, sub, target-s[i], i+1, result)
            sub.pop()