Python backtracking beating 84%


  • 0
    Y
    def _subset_sum(xs, rem, res=None, cand=None, last=0):
        if res is None:
            res = []
        if cand is None:
            cand = []
        if not rem:
            res.append(cand[:])
        else:
            for n in xs:
                next_rem = rem - n
                if next_rem < 0 or last > n:
                    continue
                cand.append(n)
                _subset_sum(xs, next_rem, res, cand, n)
                cand.pop()
        return res
    
    
    def subset_sum(xs, rem):
        # https://leetcode.com/problems/combination-sum/description/
        xs.sort()
        return _subset_sum(xs, rem)
    

Log in to reply
 

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