377. Combination Sum IV Medium

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

Approach

Input: An array of distinct integers nums, a target integer target.

Output: Return the number of combinations that sum to target.

This problem belongs to Linear DP problems.

1. Abstracting into Dynamic Programming

This problem asks: use numbers in nums to form combinations summing to target, different sequences count as different combinations.

• The total target can be formed from combinations of target - num;

2. State Definition

Let dp[i] represent the total number of combinations to form integer i (different sequences are considered different combinations).

3. State Transition Equation

The goal is dp[i], which can come from all previous dp[i - num]:

• If you want to use num to form i, then i - num must already have a valid combination;
• Every num can be tried to be appended at the end of combinations;

So: dp[i] = dp[i - num_1] + dp[i - num_2] + ... (only adding those where i - num >= 0)

4. Initial Conditions

dp[0] = 1 # Because making 0 has only one way, which is picking nothing

5. Target Value

The final answer is dp[target]

Implementation

python

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        # Initialize dp array, dp[i] denotes the number of combinations adding up to i
        dp = [0] * (target + 1)
        # 1 way to form the sum 0 (by completely skipping elements)
        dp[0] = 1

        # Iterate through every sum up to target
        for i in range(1, target + 1):
            # Try applying every number in nums
            for num in nums:
                # If the sum i is greater than or equal to num, it implies num can participate in forming the sum
                if i >= num:
                    # Accumulate combinations dynamically relying on values assigned prior to adding num
                    dp[i] += dp[i - num]

        # Returns combinations for targeting values
        return dp[target]

javascript

/**
 * @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 + 1; i++) {
        for (let num of nums) {
            if (i >= num) {
                dp[i] += dp[i - num];
            }
        }
    }

    return dp[target];
};

Complexity Analysis

• Time Complexity: O(n * target)
• Space Complexity: O(target)

Links

377. Combination Sum IV (English)

377. 组合总和 Ⅳ (Chinese)