Python 6-liner DP, 54ms

  • 0
    class Solution(object):
        def combinationSum4(self, nums, target):
            dic,dp = set(nums),[0]*target
            for i in range(target):
                dp[i] = dp[i]+1 if i+1 in dic else dp[i]
                for n in [n for n in dic if i >= n]:
                    dp[i] += dp[i-n]
            return dp[-1]

Log in to reply

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