# 377 - Combination Sum IV

這題乍看之下是 unbounded knapsack，但 recurrence formula 寫起來跟 Unbounded Knapsack 的幾題都不太一樣，比較屬於 Fibonacci Number 的 pattern。

這一篇 discussion post 寫得很好：

Think about the recurrence relation first. How does the # of combinations of the target related to the # of combinations of numbers that are smaller than the target?

So we know that target is the sum of numbers in the array. Imagine we only need one more number to reach target, this number can be any one in the array, right? So the # of combinations of target, comb[target] = sum(comb[target - nums[i]]), where 0 <= i < nums.length, and target >= nums[i].

In the example given, we can actually find the # of combinations of 4 with the # of combinations of 3(4 - 1), 2(4- 2) and 1(4 - 3). As a result, comb[4] = comb[4-1] + comb[4-2] + comb[4-3] = comb[3] + comb[2] + comb[1].

Then think about the base case. Since if the target is 0, there is only one way to get zero, which is using 0, we can set comb[0] = 1.

實作如下：

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        // use uint64_t to prevent int overflow
        vector<uint64_t> dp(target+1);
        dp[0] = 1;

        for (int i=1; i<=target; i++) {
            for (int j=0; j<nums.size(); j++) {
                int prev = i - nums[j];
                if (prev >= 0) dp[i] += dp[prev];
            }
        }
        return dp[target];
    }
};