7-liner in Python, and follow-up question


  • 27
    class Solution(object):
        def combinationSum4(self, nums, target):
            nums, combs = sorted(nums), [1] + [0] * (target)
            for i in range(target + 1):
                for num in nums:
                    if num  > i: break
                    if num == i: combs[i] += 1
                    if num  < i: combs[i] += combs[i - num]
            return combs[target]
    
    # 17 / 17 test cases passed.
    # Status: Accepted
    # Runtime: 116 ms
    

    This is a 4-line top-down solution that doesn't get accepted due to recursion limit.

    class Solution(object):
        def combinationSum4(self, nums, target, memo=collections.defaultdict(int)):
            if target < 0: return 0
            if target not in memo:
                memo[target] += sum((1, self.combinationSum4(nums, target - num))[target != num] 
                                    for num in nums)
            return memo[target]
    

    The problem with negative numbers is that now the combinations could be potentially of infinite length. Think about nums = [-1, 1] and target = 1. We can have all sequences of arbitrary length that follow the patterns -1, 1, -1, 1, ..., -1, 1, 1 and 1, -1, 1, -1, ..., 1, -1, 1 (there are also others, of course, just to give an example). So we should limit the length of the combination sequence, so as to give a bound to the problem.

    This is a recursive Python code that solves the above follow-up problem, so far it's passed all my test cases but comments are welcome.

    class Solution(object):
        def combinationSum4WithLength(self, nums, target, length, memo=collections.defaultdict(int)):
            if length <= 0: return 0
            if length == 1: return 1 * (target in nums)
            if (target, length) not in memo: 
                for num in nums:
                    memo[target, length] += self.combinationSum4(nums, target - num, length - 1)
            return memo[target, length]
    

  • 0

    Why not the usual combs = [1] + [0] * target?


  • 1
    A
    class Solution(object):
        def combinationSum4(self, nums, target):
            nums.sort()
            dp = [1] + [0] * target
            for i in xrange(target+1):
                for n in nums:
                    if i + n > target:
                        break
                    dp[i+n] += dp[i]
            return dp[-1]
    

  • 0

    @ac said in 7-liner in Python, and follow-up question:

    '''
    class Solution(object):
    def combinationSum4(self, nums, target):
    nums.sort()
    dp = [1] + [0] * target
    for i in xrange(target+1):
    for n in nums:
    if i + n > target:
    break
    dp[i+n] += dp[i]
    return dp[-1]
    '''

    @ac you have to use the "`" character, not the ' to send code.


  • 0
    A

    @agave thanks. revised.


  • 4

    @agave I see you did change combs[0] to 1, but you're not taking advantage of it. You're not even accessing it at all.


  • 2
    D
    def combinationSum4(self, nums, target):
            dp = [1] + [0] * target
            for i in range(1, target + 1):
                dp[i] = sum([dp[i - c] for c in nums if i >= c])
            return dp[-1]
    

  • 3

    Regarding the follow-up, how about limiting each number in array to be used only once? Then DP won't work anymore.


  • 1
    D

    Improved code.

        def combinationSum4(self, nums, target):
            nums, combs = sorted(nums), [1] + [0] * (target)
            for i in range(target + 1):
                for num in nums:
                    if num  > i: break
                    combs[i] += combs[i - num]
            return combs[target]
    

  • 1
    X

    @agave

    your code for the followup is not correct

    class Solution(object):
        def combinationSum4WithLength(self, nums, target, length, memo=collections.defaultdict(int)):
            if length <= 0: return 0
            if length == 1: return 1 * (target in nums)
            if (target, length) not in memo: 
                for num in nums:           
                    memo[target, length] += self.combinationSum4(nums, target - num, length - 1)
            return memo[target, length]
    

    The recursive call name is not correct, even if it is correct, the results will also be wrong.
    For example:

    nums = [-1,1,2,3], target = 3, length_limit = 2
    

    the combinations should be:

    • [1,2]
    • [2,1]
    • [3]

    The answer should be 3, but your code will return 2.


Log in to reply
 

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