LeetCodee

377. Combination Sum IV

Jump to Solution: Python Java C++ JavaScript C#

Problem Description

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

The test cases are generated so that the answer can fit in a 32-bit integer.

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

Constraints:

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 1000
  • All the elements of nums are unique
  • 1 <= target <= 1000

Solution

Python Solution

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        # dp[i] represents the number of combinations that sum up to i
        dp = [0] * (target + 1)
        dp[0] = 1  # Empty combination
        
        # For each sum from 1 to target
        for i in range(1, target + 1):
            # Try to add each number from nums
            for num in nums:
                if i >= num:
                    dp[i] += dp[i - num]
        
        return dp[target]

Time Complexity: O(target * n)

Where n is the length of nums array. We need to try each number for each target sum.

Space Complexity: O(target)

For the dynamic programming array.

Java Solution

class Solution {
    public int combinationSum4(int[] nums, int target) {
        // dp[i] represents the number of combinations that sum up to i
        int[] dp = new int[target + 1];
        dp[0] = 1;  // Empty combination
        
        // For each sum from 1 to target
        for (int i = 1; i <= target; i++) {
            // Try to add each number from nums
            for (int num : nums) {
                if (i >= num) {
                    dp[i] += dp[i - num];
                }
            }
        }
        
        return dp[target];
    }
}

Time Complexity: O(target * n)

Where n is the length of nums array. We need to try each number for each target sum.

Space Complexity: O(target)

For the dynamic programming array.

C++ Solution

class Solution {
public:
    int combinationSum4(vector& nums, int target) {
        // dp[i] represents the number of combinations that sum up to i
        vector dp(target + 1, 0);
        dp[0] = 1;  // Empty combination
        
        // For each sum from 1 to target
        for (int i = 1; i <= target; i++) {
            // Try to add each number from nums
            for (int num : nums) {
                if (i >= num) {
                    dp[i] += dp[i - num];
                }
            }
        }
        
        return dp[target];
    }
};

Time Complexity: O(target * n)

Where n is the length of nums array. We need to try each number for each target sum.

Space Complexity: O(target)

For the dynamic programming array.

JavaScript Solution

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var combinationSum4 = function(nums, target) {
    // dp[i] represents the number of combinations that sum up to i
    const dp = new Array(target + 1).fill(0);
    dp[0] = 1;  // Empty combination
    
    // For each sum from 1 to target
    for (let i = 1; i <= target; i++) {
        // Try to add each number from nums
        for (const num of nums) {
            if (i >= num) {
                dp[i] += dp[i - num];
            }
        }
    }
    
    return dp[target];
};

Time Complexity: O(target * n)

Where n is the length of nums array. We need to try each number for each target sum.

Space Complexity: O(target)

For the dynamic programming array.

C# Solution

public class Solution {
    public int CombinationSum4(int[] nums, int target) {
        // dp[i] represents the number of combinations that sum up to i
        int[] dp = new int[target + 1];
        dp[0] = 1;  // Empty combination
        
        // For each sum from 1 to target
        for (int i = 1; i <= target; i++) {
            // Try to add each number from nums
            foreach (int num in nums) {
                if (i >= num) {
                    dp[i] += dp[i - num];
                }
            }
        }
        
        return dp[target];
    }
}

Time Complexity: O(target * n)

Where n is the length of nums array. We need to try each number for each target sum.

Space Complexity: O(target)

For the dynamic programming array.

Approach Explanation

The solution uses dynamic programming to count all possible combinations:

  1. Key Insights:
    • Order matters (different sequences count)
    • Numbers can be reused
    • Bottom-up approach
    • Subproblem overlapping
  2. Algorithm Steps:
    • Initialize DP array
    • Process each target sum
    • Try each number for each sum
    • Accumulate combinations

Implementation Details:

  • Handle base case (empty sum)
  • Process sums in order
  • Consider all numbers
  • Maintain running totals

Optimization Insights:

  • Early pruning
  • Space optimization
  • Order independence
  • Efficient state transitions

Edge Cases:

  • Empty array
  • Target smaller than all numbers
  • Single number array
  • Large target values