Python solution that beats 96% by sorting the input first

  • 0

    My idea is very straightforward. We first sort the array from small to big. For each number in the sorted array, we consider EITHER including it (so target-=input[0] and array doesn't change) OR not including it (so target stays same, but array removes the first element).

    Throughout the recursion, we consider 3 edge cases:>array[0]

    1. target==array[0]

    In the first 2 cases, it returns a []. In case 3, it returns [array[0]]

    Below is the code

    class Solution(object):
        def combinationSum(self, candidates, target):
            def helper(lego,target):
                if lego==[]:
                    return []
                if target<lego[0]:
                    return []
                if target==lego[0]:
                    return [[lego[0]]]
                return [[lego[0]]+a for a in helper(lego, target-lego[0])]+helper(lego[1:], target)
            return helper(legos,target)

Log in to reply

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