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 the 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 the nums array. For each number num in nums:

3. Inner Iteration: Iterate from num to target in the dp array. For each index i, update dp[i] by adding dp[i - num]. This represents adding the current num to all the combinations that sum up to i - num.

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

Explanation

This solution uses dynamic programming. The key idea is to build up the solution incrementally. dp[i] represents the number of combinations that add up to i. When we consider a new number num, we can add it to all previously found combinations that sum to i - num to find new combinations that sum to i. The process is efficient because we avoid redundant calculations by storing and reusing intermediate results.

Code

public class Solution {
    public int CombinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;

        for (int i = 1; i <= target; i++) {
            foreach (int num in nums) {
                if (i >= num) {
                    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 up to target.

• Space Complexity: O(target). The dp array has a size of target + 1.