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 the numbers 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. Dynamic Programming Approach: We'll use dynamic programming to solve this problem efficiently. We create a DP array dp of size target + 1, where dp[i] represents the number of combinations that sum up to i.

2. Base Case: dp[0] = 1 because there's one way to obtain a sum of 0 (using no numbers).

3. Iteration: We iterate through each number num in nums and then iterate through the dp array from num to target. For each i, we add dp[i - num] to dp[i]. This represents adding the current num to all the combinations that previously summed to i - num.

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

Explanation

The core idea is that to reach a target sum i, we can use any of the numbers in nums as the last number added. If we use num as the last number, then the remaining sum is i - num. The number of ways to reach i - num is given by dp[i - num]. Therefore, to find the total number of ways to reach i, we sum the number of ways to reach i - num for all num in nums.

This approach avoids redundant calculations by storing the intermediate results in the dp array.

Code

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1; // Base case: one way to reach sum 0

        for (int i = 1; i <= target; i++) {
            for (int num : nums) {
                if (i - num >= 0) {
                    dp[i] += dp[i - num];
                }
            }
        }

        return dp[target];
    }
}

Complexity

• Time Complexity: O(N * target), where N is the length of nums. We have nested loops iterating through nums and the dp array.

• Space Complexity: O(target). The space used is dominated by the dp array.