Combination Sum IV

LeetCode 377: Combination Sum IV Solution & Explanation

Problem Overview

TL;DR: The optimal solution uses a 1D Dynamic Programming array where dp[i] accumulates the number of ways to reach target i by summing up ways to reach i - num for every number in the input array.

In the LeetCode 377 problem, titled Combination Sum IV, we are provided with an array of distinct integers nums and a target integer target. Our goal is to determine the total number of possible sequences of numbers from nums that sum up to target.

It is crucial to note that, unlike standard mathematical combinations, the order of elements in the sequence matters here. For example, the sequence (1, 2) is considered distinct from (2, 1). This makes the problem technically about finding permutations with replacement, despite the title. This is a popular interview question that tests your understanding of Dynamic Programming state transitions and loop ordering.

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.

1# Pseudo-code for Brute Force
2def count(target):
3    if target == 0: return 1
4    if target < 0: return 0
5    res = 0
6    for num in nums:
7        res += count(target - num)
8    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.

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.

Pattern Reuse Notes

The Dynamic Programming - 1D Array pattern used here is highly versatile.

• LeetCode 322: Coin Change: Uses the same 1D array structure but minimizes the count (min) instead of summing ways (sum).
• LeetCode 518: Coin Change II: Uses the same 1D array but swaps the loop order (outer nums, inner target) to count combinations where order does not matter.

Reference Implementation

C++ Solution for LeetCode 377

1class Solution {
2public:
3    int combinationSum4(vector<int>& nums, int target) {
4        // dp[i] stores the number of ways to get sum 'i'
5        // Using unsigned int to prevent potential overflow during intermediate additions
6        // though the problem guarantees the final answer fits in a 32-bit signed int.
7        vector<unsigned int> dp(target + 1, 0);
8        
9        dp[0] = 1; // Base case: one way to get 0 (empty set)
10        
11        // Outer loop iterates through all targets from 1 to target
12        for (int i = 1; i <= target; ++i) {
13            // Inner loop iterates through all numbers
14            for (int num : nums) {
15                if (i >= num) {
16                    dp[i] += dp[i - num];
17                }
18            }
19        }
20        
21        return dp[target];
22    }
23};

Java Solution for LeetCode 377

1class Solution {
2    public int combinationSum4(int[] nums, int target) {
3        // dp[i] will store the number of combinations that sum up to i
4        int[] dp = new int[target + 1];
5        
6        // Base case: There is one way to reach target 0 (using no numbers)
7        dp[0] = 1;
8        
9        // Iterate through all target values from 1 to target
10        for (int i = 1; i <= target; i++) {
11            // Check every number in nums to see if it can be the last element added
12            for (int num : nums) {
13                if (i >= num) {
14                    dp[i] += dp[i - num];
15                }
16            }
17        }
18        
19        return dp[target];
20    }
21}

Python Solution for LeetCode 377

1class Solution:
2    def combinationSum4(self, nums: List[int], target: int) -> int:
3        # Initialize DP array where dp[i] is the number of ways to reach sum i
4        dp = [0] * (target + 1)
5        
6        # Base case
7        dp[0] = 1
8        
9        # Iterate through all targets from 1 to target
10        for i in range(1, target + 1):
11            # Iterate through each number in nums
12            for num in nums:
13                if i >= num:
14                    dp[i] += dp[i - num]
15                    
16        return dp[target]