(nums []int, target int)
| 1 | package combination_sum_iv_377 |
| 2 | |
| 3 | func combinationSum4(nums []int, target int) int { |
| 4 | dp := make([]int, target+1) |
| 5 | dp[0] = 1 |
| 6 | |
| 7 | // for each number up to and including target |
| 8 | for i := 1; i <= target; i++ { |
| 9 | |
| 10 | // for each number in nums we can pick from |
| 11 | for _, n := range nums { |
| 12 | if n > i { |
| 13 | continue |
| 14 | } |
| 15 | |
| 16 | // dp[i] is equal to the sum of past |
| 17 | // dp values by choosing each number |
| 18 | // n to try to make up the current |
| 19 | // target i. See notes for table |
| 20 | // explanation. |
| 21 | dp[i] += dp[i-n] |
| 22 | } |
| 23 | } |
| 24 | |
| 25 | return dp[len(dp)-1] |
| 26 | } |
no outgoing calls