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 in the combination.

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 achieve 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 is because if we can achieve a sum of i - num, we can add num to it to achieve a sum of i.

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

Explanation

The dynamic programming approach efficiently avoids redundant calculations. Instead of recursively exploring all possible combinations (which would lead to exponential time complexity), it builds up a solution bottom-up. Each dp[i] is calculated only once, and it leverages the previously computed values dp[i - num] to determine the number of combinations that sum to i. This bottom-up approach ensures that we explore every possible combination exactly once.

Code

#include <vector>

using namespace std;

int combinationSum4(vector<int>& nums, int target) {
    vector<long long> dp(target + 1, 0); // Use long long to prevent integer overflow
    dp[0] = 1;

    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 and target is the target sum. We have nested loops iterating through nums and dp.
• Space Complexity: O(target). The space used by the dp array is proportional to the target value.