377. Combination Sum IV

Description

The problem involves calculating the number of possible combinations that add up to a target value using a set of integers. This is a classic dynamic programming problem where the objective is to find the number of ways to achieve a specific target using elements from a given set. Each number from the set can be used as many times as necessary.

Intuition

The intuition behind solving this problem is to break it down into subproblems. For each target value, we calculate how many combinations can be formed using numbers smaller or equal to that target. If we know the number of ways to form a smaller target, we can add the ways that include the current number to form the larger target. The problem resembles finding permutations rather than combinations since the order of numbers matters.

Approach

1. Dynamic Programming Array: Create a dp array of size target + 1, where dp[i] stores the number of ways to form the target i using the available numbers.
2. Initialization: Initialize dp[0] = 1 because there's only one way to get a sum of 0, which is by using no numbers.
3. Filling the DP Array: Loop through all possible target values from 1 to target. For each value, check all available numbers from the input array. If the number can be used (i.e., it is less than or equal to the current target value), then add the number of ways to form the remainder (i - num) to dp[i].
4. Return the Result: The final result will be stored in dp[target], which gives the number of ways to reach the target using the given numbers.

Complexity

Time Complexity:

O(n * target), where n is the length of the input array. For each target value, we iterate through all numbers in the array.

Space Complexity:

O(target), because we use a dynamic programming array of size target + 1.

Code

C++

class Solution {
public:
    int combinationSum4(vector& nums, int target) {
        vector dp(target + 1, 0);  // Use long long for safety
        dp[0] = 1;

        for (int i = 1; i <= target; ++i) {
            for (int n : nums) {
                if (n <= i) {
                    // Check for potential overflow
                    if (dp[i] > INT_MAX - dp[i - n]) {
                        dp[i] = INT_MAX;  // Cap the value to INT_MAX
                    } else {
                        dp[i] += dp[i - n];
                    }
                }
            }
        }

        return (dp[target] > INT_MAX) ? INT_MAX : (int)dp[target];
    }
};

Python

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [0] * (target + 1)
        dp[0] = 1

        for i in range(1, target + 1):
            for n in nums:
                if n <= i:
                    dp[i] += dp[i - n]

        return dp[target]

Java

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++) {
            for (int n : nums) {
                if (n <= i) {
                    dp[i] += dp[i - n];
                }
            }
        }

        return dp[target];
    }
}

JavaScript

var combinationSum4 = function (nums, target) {
    const dp = new Array(target + 1).fill(0);
    dp[0] = 1;

    for (let i = 1; i <= target; i++) {
        for (const n of nums) {
            if (n <= i) {
                dp[i] += dp[i - n];
            }
        }
    }

    return dp[target];
};