Combination Sum IV

Problem

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

The test cases are generated so that the answer can fit in a 32-bit integer.

Example 1:

Input: nums = [1,2,3], target = 4
Output: 7
Explanation:
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.

Example 2:

Input: nums = [9], target = 3
Output: 0

Constraints:

1 <= nums.length <= 200
1 <= nums[i] <= 1000
All the elements of nums are unique.
1 <= target <= 1000

Solution

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var combinationSum4 = function(nums, target) {
    const dp = Array(target + 1).fill(0);
    dp[0] = 1;

    for (let i = 1; i <= target; i++) {
        for (const n of nums) {
            if (n <= i) {
                dp[i] += dp[i - n];
            }
        }
    }
    return dp[target];
};

Note that this question asks for "combinations", but really means "permutations" (ie. (1, 1, 2) and (2, 1, 1) are different). The actual "combinations" version of the question is Coin Change 2.

We will implement a DP solution. Let dp[i] be the number of permutations using values in nums that adds up to i (once we reach the end of nums for the inner-loop).

For the base case, if i = 0, then dp[0] = 0, since there's only 1 way to add up to 0, which is the empty set.
For the recursive case, ... (I have no idea how this works)

This question is similar to the optimized solution of Coin Change 2, except the order of the two loops are swapped to allow duplicates (ie. permutation vs. combination).

Problem​

Solution​

Problem

Solution