Brute Force Approach for Combination Sum IV

The brute force approach attempts to build every possible sequence that sums to the target using recursion. At any current sum, we branch out by trying to add every available number from nums to the sequence.

Naive Recursive Logic

We define a function count(remaining_target):

1. Base Case Success: If remaining_target == 0, we have found a valid sequence. Return 1.
2. Base Case Failure: If remaining_target < 0, the sequence is invalid. Return 0.
3. Recursive Step: Iterate through each number in nums. The total count for the current state is the sum of count(remaining_target - num) for all num.

python
# Pseudo-code for Brute Force
def count(target):
    if target == 0: return 1
    if target < 0: return 0
    res = 0
    for num in nums:
        res += count(target - num)
    return res

Time Complexity Analysis

The time complexity is exponential, roughly $O(N^T)$, where $N$ is the length of nums and $T$ is the target. This occurs because the recursion tree branches $N$ times at each step, potentially reaching a depth of target (if 1 is in nums).

Why It Fails

This approach fails due to Time Limit Exceeded (TLE) errors. The recursion solves the same subproblems repeatedly. For example, to calculate ways to reach 5, we might calculate ways to reach 3 multiple times (e.g., via $1+1+...$ or $2+...$). Without memoization or tabulation, the redundant computations make this infeasible for targets up to 1000.

Core Insight for Combination Sum IV

The key intuition is to reverse the direction of the brute force approach. Instead of starting from target and breaking it down, we build up from 0 to target.

To find the number of sequences that sum to i, consider the last number added to the sequence. If the last number was x (where x is in nums), then the sequence prior to adding x must have summed to i - x. Therefore, the total ways to reach i is the sum of ways to reach i - x for all valid x.

The Invariant: dp[i] = sum(dp[i - num]) for all num in nums where i >= num.

Visual Description: Imagine a 1D array dp of size target + 1. We initialize dp[0] to 1, representing the single way to reach a sum of 0 (the empty sequence). We then iterate through every integer from 1 up to target. For each integer i (the current sub-target), we look backward at indices i - num for every num available in our input list. We take the values stored at those prior indices and add them to the current index dp[i]. This process effectively "pulls" the counts from previous states forward, aggregating all valid paths that land on i.

Algorithm Strategy: DP - 1D Array (Coin Change / Unbounded Knapsack Style)

1. State Definition: Create an array dp of size target + 1. dp[i] will store the number of possible combinations that add up to i.
2. Initialization: Set dp[0] = 1. This is the base case: there is exactly one way to get a sum of 0 (by choosing nothing). All other indices start at 0.
3. Iteration Order (Crucial):
   • The outer loop iterates through all target values from 1 to target.
   • The inner loop iterates through each number in nums.
   • Note: This specific loop order (target outer, nums inner) ensures we count permutations. If we swapped the loops, we would count combinations (where order doesn't matter), which is the solution for Coin Change II but incorrect for Combination Sum IV.
4. Transition: For every i (current target) and num (current candidate), if i >= num, update dp[i] += dp[i - num].
5. Result: The value at dp[target] contains the answer.

Execution Flow

Let's trace nums = [1, 2, 3] and target = 4.

1. Init: dp array of size 5: [1, 0, 0, 0, 0].
2. i = 1:
   • num=1: dp[1] += dp[0] (1) $\rightarrow$ dp is [1, 1, 0, 0, 0].
   • num=2, 3: ignored (greater than i).
3. i = 2:
   • num=1: dp[2] += dp[1] (1).
   • num=2: dp[2] += dp[0] (1).
   • dp is [1, 1, 2, 0, 0]. (Ways: 1+1, 2)
4. i = 3:
   • num=1: dp[3] += dp[2] (2).
   • num=2: dp[3] += dp[1] (1).
   • num=3: dp[3] += dp[0] (1).
   • dp is [1, 1, 2, 4, 0]. (Ways: 1+1+1, 2+1, 1+2, 3)
5. i = 4:
   • num=1: dp[4] += dp[3] (4).
   • num=2: dp[4] += dp[2] (2).
   • num=3: dp[4] += dp[1] (1).
   • dp is [1, 1, 2, 4, 7].
6. Return: dp[4] which is 7.

Proof of Correctness

The algorithm is correct by induction.

• Base Case: dp[0] = 1 correctly represents the single empty set summing to 0.
• Inductive Step: Assume dp[k] is correct for all $k < i$. The set of all sequences summing to i can be partitioned based on the last element added. If the last element is num, the prefix must sum to i - num. Since nums contains distinct integers, these partitions are disjoint. By summing dp[i - num] for all valid num, we account for every possible last step exactly once.
• Conclusion: dp[target] accumulates the total count of valid sequences.

Reference Implementation

C++ Solution for LeetCode 377

cpp
class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        // dp[i] stores the number of ways to get sum 'i'
        // Using unsigned int to prevent potential overflow during intermediate additions
        // though the problem guarantees the final answer fits in a 32-bit signed int.
        vector<unsigned int> dp(target + 1, 0);
        
        dp[0] = 1; // Base case: one way to get 0 (empty set)
        
        // Outer loop iterates through all targets from 1 to target
        for (int i = 1; i <= target; ++i) {
            // Inner loop iterates through all numbers
            for (int num : nums) {
                if (i >= num) {
                    dp[i] += dp[i - num];
                }
            }
        }
        
        return dp[target];
    }
};

Java Solution for LeetCode 377

java
class Solution {
    public int combinationSum4(int[] nums, int target) {
        // dp[i] will store the number of combinations that sum up to i
        int[] dp = new int[target + 1];
        
        // Base case: There is one way to reach target 0 (using no numbers)
        dp[0] = 1;
        
        // Iterate through all target values from 1 to target
        for (int i = 1; i <= target; i++) {
            // Check every number in nums to see if it can be the last element added
            for (int num : nums) {
                if (i >= num) {
                    dp[i] += dp[i - num];
                }
            }
        }
        
        return dp[target];
    }
}

Python Solution for LeetCode 377

python
class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        # Initialize DP array where dp[i] is the number of ways to reach sum i
        dp = [0] * (target + 1)
        
        # Base case
        dp[0] = 1
        
        # Iterate through all targets from 1 to target
        for i in range(1, target + 1):
            # Iterate through each number in nums
            for num in nums:
                if i >= num:
                    dp[i] += dp[i - num]
                    
        return dp[target]