Leetcode 40. Combination Sum II

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

Slightly different from last problem, but we can still do it using DFS. This solution is very similar with last problem's.

Solution:

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

Run Time: 136 ms