Combination Sum – Python 3 (Week 17 – 01)

class Solution:
    """
    @param candidates: A list of integers
    @param target: An integer
    @return: A list of lists of integers
    """
    
    #complexity O(s*n) s max < 2^n
    def combinationSum(self, candidates, target):
        # write your code here
        candidates = sorted(list(set(candidates)))
        results = []
        self.dfs(candidates, target, 0, [], results)
        return results
        
        
    def dfs(self, candidates, target, start, combination, results):
        if target < 0:
            return
        
        if target == 0:
            return results.append(list(combination))
            
        for i in range(start, len(candidates)):
            combination.append(candidates[i])
            self.dfs(candidates, target - candidates[i], i, combination, results)
            combination.pop()