Combination Sum IV

377.Combination Sum IV

Array

Dynamic Programming

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 order of the combination matters.

Example:

Input:

nums = [1,2,3], target = 4

→

Output:

7

Algorithm:

1. Create DP array size target + 1
2. Initialize dp[0] = 1 for empty sum
3. For each sum, try all numbers
4. Add combinations from smaller sums

Complexity:

Time: O(target * n) | Space: O(target)

Java Solution:

public int combinationSum4(int[] nums, int target) {
    int[] dp = new int[target + 1];
    dp[0] = 1;  // Base case: one way to make sum 0
    
    for (int i = 1; i <= target; i++) {
        for (int num : nums) 
            if (i - num >= 0)  // Check if can use current number
                dp[i] += dp[i - num];  // Add combinations from previous sum
    }
    
    return dp[target];
}

Python Solution:

def combinationSum4(self, nums: List[int], target: int) -> int:
    dp = [0] * (target + 1)
    dp[0] = 1  # Base case: one way to make sum 0
    
    for i in range(1, target + 1):
        for num in nums:
            if i - num >= 0:
                dp[i] += dp[i - num]
    
    return dp[target]

C++ Solution:

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<unsigned long> dp(target + 1, 0);
        dp[0] = 1;  // Base case: one way to make sum 0
        
        for(int i = 1; i <= target; i++) {
            for(int num : nums) {
                if(i >= num) {
                    dp[i] += dp[i - num];
                }
            }
        }
        
        return dp[target];
    }
};