Leetcode 39. Combination Sum

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

DFS.

Solution:

# T:O(k*n^k) S:O(k)
class Solution:
    # @param {integer[]} candidates
    # @param {integer} target
    # @return {integer[][]}
    def dfs(self, candidates, target, start, valueList):
        L = len(candidates)
        if target == 0:
            Solution.ret.append(valueList)
        for i in xrange(start, L):
            if target < candidates[i]:
                return
            self.dfs(candidates, target - candidates[i], i, valueList + [candidates[i]])
        
    def combinationSum(self, candidates, target):
        candidates.sort()
        Solution.ret = []
        self.dfs(candidates, target, 0, [])
        return Solution.ret

Run Time: 92 ms