Python 96ms DFS with pruning solution


  • 0
    W
    class Solution(object):
        def _func(self, cands, tar, cur_l, cur_i, res):
            # print "cur_l:{0}\ncur_v:{1}\tcur_i:{2}".format(cur_l, cur_v, cur_i)
            if tar <= 0:
                if tar == 0:
                    res.append(cur_l)
                return -1
            else:
                for i in xrange(cur_i, len(cands)):
                    v = cands[i]
                    self._func(cands, tar-v, cur_l+[v], i, res) == -1: 
                        break
                return 0
    
        def combinationSum(self, candidates, target):
            """
            :type candidates: List[int]
            :type target: int
            :rtype: List[List[int]]
            """
            candidates.sort()
            res = []
            self._func(candidates, target, [], 0, res)
            return res

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.