377. Combination Sum IV

Description:

Solution:

For this problem, we are gonna use hashmap. 

ex) nums = [1, 2, 3], target = 4

dp[0] = 1

dp[1] = dp[1] + dp[1-1] + dp[1-2] + dp[1-3] = 0 + 1 + 0 + 0 = 1

dp[2] = dp[2] + dp[2-1] + dp[2-2] + dp[2-3] = 0 + 1 + 1 + 0 = 2

dp[3] = dp[3] + dp[3-1] + dp[3-2] + dp[3-3] = 0 + 2 + 1 + 1 = 4

dp[4] = dp[4] + dp[4-1] + dp[4-2] + dp[4-3] = 0 + 4 + 2 + 1 = 7

 

∵ dp[target] = 7

 

Time Complexity: O(mn)

Space Complexity: O(mn)