[LeetCode] 40. Combination Sum II

Problem :  https://leetcode.com/problems/combination-sum-ii/

Should sort the candidates array first and skip candidate which has same value as its previous one to avoid duplicate result

class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        
        result = []
        L = len(candidates)
        candidates.sort()
        
        def backtracking(start, partial, n):
            if n == 0:
                if partial:
                    result.append(partial)
                    
            for i in range(start, L):
                if n - candidates[i] < 0:
                    break
                
                # skip candidates with same value to avoid duplicate result
                if i > start and candidates[i] == candidates[i-1]:
                    continue
                
                backtracking(i + 1, partial + [candidates[i]], n - candidates[i])
            
        backtracking(0, [], target)
        
        return result