Leecode Combination Sum IV

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

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

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

We can still apply the DFS method to count this, however, the cost will be too high that can't pass the time limit. This case is similar to the coin exchange problem. We can use dynamic programming concept to reuse the product during the process.

The code is also quite similar to coin exchange problem.

    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target + 1);
        dp[0] = 1;
        for (int i = 1; i <= target; ++i) {
            for (int x : nums) {
                if (i >= x) {
                    dp[i] += dp[i - x];
                }
            }
        }
        
        return dp[target];
    }

Noted that in Coin exchange problem 

dp[0] = 0. The definition was "the minimum coins used to combine the value", therefore

the minimum coins to combine "0" should be zero. And in coin exchange problem we initiate other elements in the vector to n+1 to make the min-comparison work.

Here,

the dp represents " all possible sets to combine the value" while we didn't initiate other elements in the vecotr. The empty set is also counted to combine the value 0 here. So dp[0] =1;