def combinationSum4(self, nums, target): dp =  +  * 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)