Skip to main content
CodePeetCodePeet
CodePeet 250

Combination Sum IV

MEDIUMProblemSolveExternal Links

Description

You are given an array of distinct positive integers nums and a target integer target. Return the number of possible ordered sequences (the problem calls them "combinations") of elements from nums that add up to target.

Two key rules:

  1. Repetition allowed: You may use the same number from nums as many times as you want.
  2. Order matters: Different orderings of the same numbers count as separate sequences. For instance, [1, 2, 1] and [2, 1, 1] are two distinct results — even though they use the same numbers.

Despite the name "Combination Sum", this problem is really counting permutations with repetition. This distinction is crucial and drives the entire solution strategy.

Examples

Example 1

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

Output: 7

Explanation: The seven ordered sequences that sum to 4 are:

  1. [1, 1, 1, 1]
  2. [1, 1, 2]
  3. [1, 2, 1]
  4. [1, 3]
  5. [2, 1, 1]
  6. [2, 2]
  7. [3, 1]

Notice how [1, 1, 2], [1, 2, 1], and [2, 1, 1] all use the same numbers {1, 1, 2} but count as three separate sequences because the ordering differs.

Example 2

Input: nums = [9], target = 3

Output: 0

Explanation: The smallest (and only) number available is 9, which already exceeds the target 3. No sequence of 9s can sum to 3, so the answer is 0.

Constraints

  • 1 ≤ nums.length ≤ 200
  • 1 ≤ nums[i] ≤ 1000
  • All elements of nums are distinct
  • 1 ≤ target ≤ 1000
  • The answer is guaranteed to fit in a 32-bit signed integer

Editorial

Brute Force

Intuition

The simplest way to count all ordered sequences is to try everything recursively. At each step, we have a remaining amount we still need to reach. We try placing every number from nums as the next element in our sequence, and if it does not exceed the remaining amount, we recurse on the smaller remaining amount.

Imagine you are filling a jar that holds exactly 4 units of water. You have cups of size 1, 2, and 3. You pick any cup, pour it in, and then ask: "How many ways can I fill the remaining space?" You keep picking cups until the jar is exactly full (remaining = 0, one valid sequence found) or you cannot fit any cup (dead end).

The base case is simple: when the remaining amount is 0, we have found one valid sequence — return 1. The total count for any remaining amount is the sum of counts from all valid recursive branches.

Step-by-Step Explanation

Let's trace the recursion for nums = [1, 2, 3], target = 4. We write f(r) to mean "number of sequences summing to r".

Step 1: Call f(4). Try each num:

  • num=1 → recurse on f(3)
  • num=2 → recurse on f(2)
  • num=3 → recurse on f(1)
  • f(4) = f(3) + f(2) + f(1)

Step 2: Solve f(3). Try each num:

  • num=1 → f(2)
  • num=2 → f(1)
  • num=3 → f(0) = 1 (base case!)
  • f(3) = f(2) + f(1) + 1

Step 3: Solve f(2) (called from f(3)). Try each num:

  • num=1 → f(1)
  • num=2 → f(0) = 1
  • num=3 → skip (3 > 2)
  • f(2) = f(1) + 1

Step 4: Solve f(1) (called from f(2)). Try each num:

  • num=1 → f(0) = 1
  • num=2 → skip (2 > 1)
  • num=3 → skip (3 > 1)
  • f(1) = 1

Step 5: Now unwind:

  • f(1) = 1
  • f(2) = f(1) + 1 = 1 + 1 = 2
  • f(3) = f(2) + f(1) + 1 = 2 + 1 + 1 = 4

Step 6: Back in f(4), we still need f(2) and f(1):

  • f(2) is recomputed from scratch → gets 2 again
  • f(1) is recomputed from scratch → gets 1 again
  • f(4) = f(3) + f(2) + f(1) = 4 + 2 + 1 = 7

Notice the waste: f(2) was computed once inside f(3) and again directly from f(4). f(1) was computed three separate times. As the target grows, this redundancy explodes exponentially.

Algorithm

  1. Define a recursive function f(remain):
    • If remain == 0: return 1 (found a valid sequence)
    • Initialize count = 0
    • For each num in nums:
      • If remain ≥ num: count += f(remain - num)
    • Return count
  2. Call f(target) and return the result

Code

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        if (target == 0) return 1;
        int count = 0;
        for (int num : nums) {
            if (target >= num) {
                count += combinationSum4(nums, target - num);
            }
        }
        return count;
    }
};
class Solution:
    def combinationSum4(self, nums: list[int], target: int) -> int:
        if target == 0:
            return 1
        count = 0
        for num in nums:
            if target >= num:
                count += self.combinationSum4(nums, target - num)
        return count
class Solution {
    public int combinationSum4(int[] nums, int target) {
        if (target == 0) return 1;
        int count = 0;
        for (int num : nums) {
            if (target >= num) {
                count += combinationSum4(nums, target - num);
            }
        }
        return count;
    }
}

Complexity Analysis

Time Complexity: O(n^(target / min_num))

At each recursive call, we branch into up to n child calls (one per number in nums). The recursion tree has depth up to target / min_num (the maximum number of elements in a sequence). With n = 200 and target = 1000, this is astronomically large — far beyond any practical time limit.

Space Complexity: O(target / min_num)

The recursion stack depth equals the longest possible sequence, which is target / min_num. With nums containing 1, this is O(target) = O(1000).

Why This Approach Is Not Efficient

The brute force recursion has a fatal flaw: overlapping subproblems. The same remaining amount is computed over and over again in different branches of the recursion tree.

For nums = [1, 2, 3] and target = 4:

  • f(1) is computed 3 times (once from f(2), once from f(3), once from f(4))
  • f(2) is computed 2 times (once from f(3), once from f(4))
  • f(0) is computed 4 times as a base case

This redundancy grows exponentially with the target. For target = 1000 with nums containing 1, the recursion tree has billions of nodes, most of which are re-computations of already-solved subproblems.

The key insight: there are only target + 1 unique subproblems (f(0), f(1), ..., f(target)). If we store each result the first time it is computed and reuse it for future calls, we eliminate all redundancy. This technique is called memoization.

Recursion tree for f(4) showing overlapping subproblems highlighted in color
Recursion tree for f(4) showing overlapping subproblems highlighted in color

Better Approach - Top-Down DP (Memoization)

Intuition

Memoization is the simplest upgrade to the brute force: keep the exact same recursion, but add a cache. Before computing f(remain), check: "Have I already solved this?" If yes, return the cached answer instantly. If no, compute it, store it in the cache, and then return.

Think of it like a student solving homework problems. Without memoization, if question 5 asks "What is f(3)?" and question 8 also asks "What is f(3)?", the student solves f(3) from scratch both times. With memoization, the student writes down the answer the first time and simply looks it up the second time.

Since there are only target + 1 unique subproblems (f(0) through f(target)), and each subproblem does O(n) work (trying each number in nums), the total work drops from exponential to O(target × n).

Step-by-Step Explanation

Let's trace the memoized recursion for nums = [1, 2, 3], target = 4.

Step 1: Call f(4). memo is empty. Try num=1 → recurse on f(3).

Step 2: Call f(3). Not in memo. Try num=1 → recurse on f(2).

Step 3: Call f(2). Not in memo. Try num=1 → recurse on f(1).

Step 4: Call f(1). Not in memo. Try num=1 → f(0) = 1 (base case). Nums 2,3 > 1, skip. f(1) = 1. Store memo[1] = 1.

Step 5: Back in f(2). Got f(1) = 1. Try num=2 → f(0) = 1. Num 3 > 2, skip. f(2) = 1 + 1 = 2. Store memo[2] = 2.

Step 6: Back in f(3). Got f(2) = 2. Try num=2 → needs f(1). CACHE HIT! memo[1] = 1. No recursion needed.

Step 7: f(3) so far = 2 + 1 = 3. Try num=3 → f(0) = 1. f(3) = 3 + 1 = 4. Store memo[3] = 4.

Step 8: Back in f(4). Got f(3) = 4. Try num=2 → needs f(2). CACHE HIT! memo[2] = 2.

Step 9: f(4) so far = 4 + 2 = 6. Try num=3 → needs f(1). CACHE HIT! memo[1] = 1.

Step 10: f(4) = 4 + 2 + 1 = 7.

Only 4 unique subproblems were fully computed (f(1) through f(4)). The 3 cache hits saved entire subtrees of redundant computation.

Memoized Recursion — Cache Hits Eliminate Redundant Work — Watch how the recursion tree grows depth-first, caching each result. When a previously solved subproblem is encountered, it resolves instantly (pruned) instead of branching into a full subtree.

Algorithm

  1. Create a memo dictionary (or array of size target+1 initialized to -1)
  2. Define dp(remain):
    • If remain == 0: return 1
    • If memo[remain] is already computed: return memo[remain]
    • count = 0
    • For each num in nums: if remain ≥ num, count += dp(remain - num)
    • Store memo[remain] = count
    • Return count
  3. Return dp(target)

Code

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> memo(target + 1, -1);
        return dp(nums, target, memo);
    }
    
private:
    int dp(vector<int>& nums, int remain, vector<int>& memo) {
        if (remain == 0) return 1;
        if (memo[remain] != -1) return memo[remain];
        
        int count = 0;
        for (int num : nums) {
            if (remain >= num) {
                count += dp(nums, remain - num, memo);
            }
        }
        return memo[remain] = count;
    }
};
class Solution:
    def combinationSum4(self, nums: list[int], target: int) -> int:
        memo = {}
        
        def dp(remain: int) -> int:
            if remain == 0:
                return 1
            if remain in memo:
                return memo[remain]
            
            count = 0
            for num in nums:
                if remain >= num:
                    count += dp(remain - num)
            
            memo[remain] = count
            return count
        
        return dp(target)
class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] memo = new int[target + 1];
        Arrays.fill(memo, -1);
        return dp(nums, target, memo);
    }
    
    private int dp(int[] nums, int remain, int[] memo) {
        if (remain == 0) return 1;
        if (memo[remain] != -1) return memo[remain];
        
        int count = 0;
        for (int num : nums) {
            if (remain >= num) {
                count += dp(nums, remain - num, memo);
            }
        }
        return memo[remain] = count;
    }
}

Complexity Analysis

Time Complexity: O(target × n)

There are target + 1 unique subproblems (f(0) through f(target)). Each subproblem iterates over all n numbers in nums, doing O(1) work per number. Each subproblem is computed exactly once and cached. Total: O(target × n). With target ≤ 1000 and n ≤ 200, that is at most 200,000 operations — extremely fast.

Space Complexity: O(target)

The memo array stores one entry per subproblem: O(target). The recursion stack can go as deep as target / min_num in the worst case (e.g., if nums contains 1, the stack depth is up to target). So total space is O(target).

Why This Approach Is Not Efficient

Memoization has the same O(target × n) time complexity as the optimal bottom-up approach, so it is efficient in theory. However, it has practical drawbacks:

1. Recursion overhead: Each recursive call has function call overhead — pushing and popping stack frames, passing arguments. For target = 1000, the recursion can go 1000 levels deep, creating 1000 stack frames.

2. Stack overflow risk: Python's default recursion limit is 1000. With target = 1000 and nums containing 1, the recursion depth equals 1000 — right at the limit. In Java and C++, very deep recursion can also exhaust the stack.

3. Top-down overhead: The recursive approach evaluates subproblems in a demand-driven order, which may lead to cache-unfriendly memory access patterns. The bottom-up approach fills the array sequentially (dp[0], dp[1], ..., dp[target]), which is perfectly cache-friendly.

The bottom-up (tabulation) approach eliminates all three issues: no recursion, no stack overflow risk, and sequential memory access.

Optimal Approach - Bottom-Up DP (Tabulation)

Intuition

Instead of starting at f(target) and recursing down to f(0), we flip the direction: start at f(0) and build upward to f(target).

Define dp[i] = the number of ordered sequences that sum to i.

Base case: dp[0] = 1. There is exactly one way to sum to 0: use no elements (the empty sequence).

Transition: For each amount i from 1 to target, and for each number num in nums:

  • If i ≥ num, then dp[i] += dp[i - num]

This says: to form amount i, we can place any valid num as the last element in the sequence. The number of ways to do this equals the number of ways to form the remaining amount i - num, which is dp[i - num]. By summing over all valid nums, we count all possible last elements.

Why does order matter here? Because the outer loop iterates over amounts (1 to target) and the inner loop iterates over nums. At each amount i, we consider placing ANY num as the last element. So [1, 2] (last element is 2) and [2, 1] (last element is 1) are counted separately — when computing dp[3], placing 2 last contributes dp[1] ways, and placing 1 last contributes dp[2] ways. These are independent contributions.

If we swapped the loops (outer = nums, inner = amounts), we would get unordered combinations (like Coin Change II) because each coin type would be processed once, enforcing a fixed ordering.

Step-by-Step Explanation

Let's trace the bottom-up DP for nums = [1, 2, 3], target = 4.

Step 1: Initialize dp = [1, 0, 0, 0, 0]. dp[0] = 1 (empty sequence).

Step 2: Compute dp[1]. Try each num:

  • num=1: dp[1] += dp[0] = 1. (Place 1 last, remaining is 0: one way.)
  • num=2: skip (2 > 1)
  • num=3: skip (3 > 1)
  • dp[1] = 1. Sequences: [1].

Step 3: Compute dp[2]. Try each num:

  • num=1: dp[2] += dp[1] = 1. (Place 1 last, remaining is 1: [1,1].)
  • num=2: dp[2] += dp[0] = 1. (Place 2 last, remaining is 0: [2].)
  • num=3: skip (3 > 2)
  • dp[2] = 2. Sequences: [1,1] and [2].

Step 4: Compute dp[3]. Try each num:

  • num=1: dp[3] += dp[2] = 2. (Place 1 last: [1,1,1] and [2,1].)
  • num=2: dp[3] += dp[1] = 1. (Place 2 last: [1,2].)
  • num=3: dp[3] += dp[0] = 1. (Place 3 last: [3].)
  • dp[3] = 4. Sequences: [1,1,1], [2,1], [1,2], [3].

Step 5: Compute dp[4]. Try each num:

  • num=1: dp[4] += dp[3] = 4. (Place 1 last: all 4 sequences for sum 3, each extended with 1.)
  • num=2: dp[4] += dp[2] = 2. (Place 2 last: [1,1,2] and [2,2].)
  • num=3: dp[4] += dp[1] = 1. (Place 3 last: [1,3].)
  • dp[4] = 7.

Result: dp[4] = 7.

Bottom-Up DP — Building the Answer Cell by Cell — Watch how each dp cell is filled by summing contributions from previously computed cells. Each num in nums contributes dp[i-num] ways to dp[i].

Algorithm

  1. Create dp array of size target + 1, initialized to 0
  2. Set dp[0] = 1 (base case: one way to sum to 0)
  3. For i from 1 to target:
    • For each num in nums:
      • If i ≥ num: dp[i] += dp[i - num]
  4. Return dp[target]

Code

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<unsigned int> dp(target + 1, 0);
        dp[0] = 1;
        
        for (int i = 1; i <= target; i++) {
            for (int num : nums) {
                if (i >= num) {
                    dp[i] += dp[i - num];
                }
            }
        }
        
        return dp[target];
    }
};
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 num in nums:
                if i >= num:
                    dp[i] += dp[i - num]
        
        return dp[target]
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 num : nums) {
                if (i >= num) {
                    dp[i] += dp[i - num];
                }
            }
        }
        
        return dp[target];
    }
}

Complexity Analysis

Time Complexity: O(target × n)

The outer loop runs target times. The inner loop iterates over all n numbers in nums. Each iteration does O(1) work (one addition and one comparison). Total: target × n operations. With target ≤ 1000 and n ≤ 200, this is at most 200,000 operations — well within any time limit.

Space Complexity: O(target)

We use a single dp array of size target + 1. No recursion stack, no hash map overhead. This is the minimal space required to store all subproblem answers.