Combination Sum IV medium

Problem Statement

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

The same number from nums may be chosen multiple times. The order of numbers in each combination does matter.

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

Steps

1. Initialization: Create a DP array dp of size target + 1 and initialize all elements to 0. dp[i] will store the number of combinations that sum up to i. Set dp[0] = 1 because there's one way to reach a sum of 0 (using no numbers).

2. Iteration: Iterate through each number num in nums.

3. Inner Iteration: For each num, iterate through the dp array from num to target. For each index i, update dp[i] by adding dp[i - num]. This is because if there are dp[i - num] ways to reach the sum i - num, there are dp[i - num] additional ways to reach the sum i by adding num.

4. Result: After iterating through all numbers in nums, dp[target] will contain the total number of combinations that sum up to target.

Explanation

This problem can be solved efficiently using dynamic programming. The key idea is to build up the solution iteratively. Each element in the dp array represents a subproblem: the number of ways to reach a particular sum. By iterating through the numbers and updating the dp array, we can avoid redundant calculations and find the solution in a bottom-up manner. The approach leverages the fact that the number of ways to reach a target sum i is the sum of the number of ways to reach i - num for all num in nums.

Code

function combinationSum4(nums: number[], target: number): number {
    const dp: number[] = new Array(target + 1).fill(0);
    dp[0] = 1; // Base case: one way to reach sum 0

    for (let num of nums) {
        for (let i = num; i <= target; i++) {
            dp[i] += dp[i - num];
        }
    }

    return dp[target];
};

Complexity

• Time Complexity: O(N*target), where N is the length of nums and target is the target sum. This is because of the nested loops.
• Space Complexity: O(target), due to the dp array.