Python DP solution

  • 0
     def combinationSum4(self, nums, target):
            dp = [1] + [0] * target
            for i in xrange(target + 1):
                for x in nums:
                    if i + x <= target:
                        dp[i + x] += dp[i]
            return dp[target]

    I think this could be another interesting follow-up:
    "What if the order of numbers doesn't matter?"
    Then this problem becomes a "coin change" problem which requires a different way to implement the DP.

    def combinationSum4(self, nums, target):
        for n in arr:
            for i in range(n, target+1):
                dp[i] += dp[i-n]
        return dp[target]

    if nums is [1, 2, 3] and target is 4, it returns 4. (4 different solutions if order of numbers doesn't matter)

Log in to reply

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