# 377 - Combination Sum IV

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 = comb[4-1] + comb[4-2] + comb[4-3] = comb + comb + comb`.

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 = 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 = 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];
}
};
``````