Another short Python solution


  • 0
    C

    Not that fast, but easy to write.

    There are only two cases:
    use the first item or not use the first

    class Solution(object):
        def combinationSum(self, candidates, target):
            """
            :type candidates: List[int]
            :type target: int
            :rtype: List[List[int]]
            """
            #candidates.sort()
            res, n = [], len(candidates)
            def dfs(sidx, tgt, path): #sidx is the start index in candidates
                if tgt == 0:
                    res.append(path)
                    return
                if tgt < 0 or sidx >= n: return
                
                dfs(sidx + 1, tgt, path) # do not use first item
                dfs(sidx, tgt-candidates[sidx], path + [candidates[sidx]]) # use first item (sidx)
            dfs(0, target,[])
            return res
    

  • 0
    C

    Also, combination sum2 can use the same method with small modification (remove duplicates / cannot use one item twice)

    class Solution(object):
        def combinationSum2(self, candidates, target):
            """
            :type candidates: List[int]
            :type target: int
            :rtype: List[List[int]]
            """
            candidates.sort()
            res, n = [], len(candidates)
            def dfs(sidx, tgt, path): #sidx is the start index in candidates
                if tgt == 0:
                    if path not in res: res.append(path)
                    return
                if sidx >= n or candidates[sidx] > tgt: return
                
                dfs(sidx + 1, tgt, path) # do not use first item
                dfs(sidx + 1, tgt-candidates[sidx], path + [candidates[sidx]]) # use first item (sidx)
            dfs(0, target,[])
            return res
    

Log in to reply
 

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