Combination Sum IV (LC 377): Counting Ordered Sequences with DP

Count the ordered sequences of numbers from a distinct array that add up to a target. Build dp[t] = sum of dp[t - num] from 0 up to target, with care for intermediate overflow. O(target * n) time, O(target) space.

Language Selection

Choose your preferred programming language

Showing: Python

Combination Sum IV

Problem Statement

You are given an array nums of distinct positive integers and a positive integer target. Count how many ordered sequences of elements from nums add up to exactly target. Each element may be used any number of times, and sequences that contain the same numbers in a different order are counted separately (so despite the name, you are counting permutations, not combinations).

The test data guarantees that the final count fits in a signed 32-bit integer.

Examples

Example 1:

Input: nums = [1,2], target = 4
Output: 5
Explanation: The sequences are (1,1,1,1), (1,1,2), (1,2,1), (2,1,1) and (2,2).

Example 2:

Input: nums = [2,3,5], target = 8
Output: 6
Explanation: (2,3,3), (3,2,3), (3,3,2), (3,5), (5,3) and (2,2,2,2).

Example 3:

Input: nums = [4], target = 6
Output: 0
Explanation: Only multiples of 4 can be formed, and 6 is not one.

Constraints

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 1000
  • All values in nums are distinct.
  • 1 <= target <= 1000
  • The answer fits in a signed 32-bit integer.

A Note on Overflow

Only the final answer is guaranteed to fit in 32 bits. Intermediate counts for smaller targets can be astronomically large. With nums = [2, 4, 6, 8, 999] and target = 999, the answer is 1 (just the sequence (999)), yet the count for 998 has 142 decimal digits.

All the counts are built purely by addition, and addition modulo 2^32 (or 2^64) gives the same remainder as exact addition. So if every intermediate value is allowed to wrap around, the final value is still the true answer modulo 2^32, and because the true answer is below 2^31, it is exactly the true answer. The code below relies on that:

  • Python: integers are unbounded, so there is nothing to handle.
  • Java, C#: int addition wraps (C# is unchecked by default; the code says unchecked explicitly).
  • Go: int is 64-bit and wraps, which is just as good.
  • C++: signed overflow is undefined behavior, so the counts are stored as unsigned int, which wraps by definition.
  • JavaScript: numbers are doubles and silently lose precision above 2^53, so each sum is reduced with >>> 0 (modulo 2^32).

A common alternative is to skip any addition that would exceed INT_MAX. That also works here, but the wraparound version is shorter and needs no special case.

Approach 1: Top-Down Recursion with Memoization

Algorithm

Think about the first number of a sequence. If it is num, the rest of the sequence must add up to target - num, and any valid sequence for that smaller sum works. So:

count(0) = 1                      (the empty sequence)
count(t) = sum of count(t - num) for every num in nums with num <= t

Without memoization this explodes exponentially, because the same remainders are reached through many different prefixes. Caching count(t) for each t makes each value computed only once.

  1. If remaining == 0, return 1.
  2. If remaining is already cached, return the cached value.
  3. Otherwise sum count(remaining - num) over every num <= remaining, cache it and return it.
  4. Answer is count(target).

The recursion can go target levels deep (for example nums = [1]), which is up to 1000 frames. That is fine on the default stacks of Java, Go, JavaScript, C# and C++, but it exceeds Python’s default recursion limit of 1000, so the Python version raises the limit.

Implementation

Python:

import sys
from typing import List

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        # Depth can reach target (e.g. nums = [1]); Python's default limit is 1000
        sys.setrecursionlimit(max(sys.getrecursionlimit(), target + 1000))
        memo = {0: 1}  # one way to make 0: the empty sequence

        def count(remaining: int) -> int:
            if remaining in memo:
                return memo[remaining]
            total = 0
            for num in nums:
                if num <= remaining:
                    total += count(remaining - num)  # num is the first element
            memo[remaining] = total
            return total

        return count(target)

Java:

class Solution {
    private int[] nums;
    private int[] memo;
    private boolean[] seen;

    public int combinationSum4(int[] nums, int target) {
        this.nums = nums;
        this.memo = new int[target + 1];
        this.seen = new boolean[target + 1];
        return count(target);
    }

    private int count(int remaining) {
        if (remaining == 0) return 1;  // the empty sequence
        if (seen[remaining]) return memo[remaining];
        int total = 0;
        for (int num : nums) {
            if (num <= remaining) {
                // May wrap for intermediate targets; the final answer is still exact
                total += count(remaining - num);
            }
        }
        seen[remaining] = true;  // separate flag: a wrapped count can be any int value
        memo[remaining] = total;
        return total;
    }
}

Go:

func combinationSum4(nums []int, target int) int {
    memo := make([]int, target+1)
    seen := make([]bool, target+1)

    var count func(remaining int) int
    count = func(remaining int) int {
        if remaining == 0 {
            return 1 // the empty sequence
        }
        if seen[remaining] {
            return memo[remaining]
        }
        total := 0
        for _, num := range nums {
            if num <= remaining {
                total += count(remaining - num) // int wraps on overflow; final answer stays exact
            }
        }
        seen[remaining] = true
        memo[remaining] = total
        return total
    }
    return count(target)
}

JavaScript:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var combinationSum4 = function(nums, target) {
    const memo = new Array(target + 1).fill(-1); // counts are kept in [0, 2^32), so -1 means "not computed"
    memo[0] = 1; // the empty sequence

    const count = (remaining) => {
        if (memo[remaining] !== -1) return memo[remaining];
        let total = 0;
        for (const num of nums) {
            if (num <= remaining) {
                // Reduce modulo 2^32 so values never exceed the exact range of a double
                total = (total + count(remaining - num)) >>> 0;
            }
        }
        memo[remaining] = total;
        return total;
    };

    return count(target);
};

C#:

public class Solution {
    private int[] nums;
    private int[] memo;
    private bool[] seen;

    public int CombinationSum4(int[] nums, int target) {
        this.nums = nums;
        memo = new int[target + 1];
        seen = new bool[target + 1];
        return Count(target);
    }

    private int Count(int remaining) {
        if (remaining == 0) return 1;  // the empty sequence
        if (seen[remaining]) return memo[remaining];
        int total = 0;
        foreach (int num in nums) {
            if (num <= remaining) {
                // Intermediate counts may wrap; the final answer is still exact
                total = unchecked(total + Count(remaining - num));
            }
        }
        seen[remaining] = true;
        memo[remaining] = total;
        return total;
    }
}

C++:

#include <vector>
using namespace std;

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        memo.assign(target + 1, 0u);
        seen.assign(target + 1, false);
        return static_cast<int>(count(nums, target));
    }

private:
    // unsigned wraps modulo 2^32 instead of overflowing (signed overflow is undefined)
    vector<unsigned int> memo;
    vector<bool> seen;

    unsigned int count(const vector<int>& nums, int remaining) {
        if (remaining == 0) return 1u;  // the empty sequence
        if (seen[remaining]) return memo[remaining];
        unsigned int total = 0;
        for (int num : nums) {
            if (num <= remaining) {
                total += count(nums, remaining - num);
            }
        }
        seen[remaining] = true;
        memo[remaining] = total;
        return total;
    }
};

Complexity Analysis

  • Time: O(target * n), where n is nums.length. Each of the target subproblems is computed once and loops over all n numbers.
  • Space: O(target) for the memo table and the recursion stack.

Approach 2: Bottom-Up DP (Optimal)

Algorithm

The same recurrence, filled iteratively from small sums to large ones, removes the recursion entirely.

  1. Create dp of size target + 1, with dp[0] = 1.
  2. For each sum t from 1 to target:
    • For each num in nums with num <= t, add dp[t - num] to dp[t].
  3. Return dp[target].

Why the loop order matters. The outer loop is over the sum and the inner loop over the numbers, so every number is allowed to be the last element for every sum, and different orders are counted separately. Swapping the loops (numbers outside, sums inside) counts each multiset only once, which is the answer to Coin Change II instead.

Implementation

Python:

from typing import List

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [0] * (target + 1)
        dp[0] = 1  # the empty sequence
        for t in range(1, target + 1):
            for num in nums:
                if num <= t:
                    dp[t] += dp[t - num]  # sequences ending in num
        return dp[target]

Java:

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;  // the empty sequence
        for (int t = 1; t <= target; t++) {
            for (int num : nums) {
                if (num <= t) {
                    // int addition wraps for huge intermediate counts; dp[target] is still exact
                    dp[t] += dp[t - num];
                }
            }
        }
        return dp[target];
    }
}

Go:

func combinationSum4(nums []int, target int) int {
    dp := make([]int, target+1)
    dp[0] = 1 // the empty sequence
    for t := 1; t <= target; t++ {
        for _, num := range nums {
            if num <= t {
                dp[t] += dp[t-num] // int wraps on overflow; dp[target] stays exact
            }
        }
    }
    return dp[target]
}

JavaScript:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var combinationSum4 = function(nums, target) {
    const dp = new Array(target + 1).fill(0);
    dp[0] = 1; // the empty sequence
    for (let t = 1; t <= target; t++) {
        for (const num of nums) {
            if (num <= t) {
                // Keep values modulo 2^32 so doubles never lose precision
                dp[t] = (dp[t] + dp[t - num]) >>> 0;
            }
        }
    }
    return dp[target];
};

C#:

public class Solution {
    public int CombinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;  // the empty sequence
        for (int t = 1; t <= target; t++) {
            foreach (int num in nums) {
                if (num <= t) {
                    // Intermediate counts may wrap; dp[target] is still exact
                    dp[t] = unchecked(dp[t] + dp[t - num]);
                }
            }
        }
        return dp[target];
    }
}

C++:

#include <vector>
using namespace std;

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        // unsigned wraps modulo 2^32 instead of overflowing (signed overflow is undefined)
        vector<unsigned int> dp(target + 1, 0u);
        dp[0] = 1;  // the empty sequence
        for (int t = 1; t <= target; t++) {
            for (int num : nums) {
                if (num <= t) {
                    dp[t] += dp[t - num];
                }
            }
        }
        return static_cast<int>(dp[target]);
    }
};

Complexity Analysis

  • Time: O(target * n). Two nested loops of target and n iterations with O(1) work inside.
  • Space: O(target) for the dp array.

Key Insights

  • Order matters, so it is a permutation count. Condition on the first (or last) element of the sequence: dp[t] = sum of dp[t - num].
  • Loop order decides what you count. Sums outside and numbers inside counts ordered sequences; numbers outside and sums inside counts unordered combinations.
  • dp[0] = 1 is the empty sequence. It is what makes dp[num] = 1 for a single-element sequence (num).
  • Overflow is a property of the intermediate values, not the answer. Wraparound arithmetic is safe here because the computation is nothing but additions and the final value is guaranteed to be small.

Edge Cases

  • Target smaller than every number: the answer is 0, for example nums = [5, 7], target = 3.
  • Target equal to one of the numbers: that single-element sequence counts as one way, plus any longer sequences.
  • nums = [1]: exactly one way for any target, and the recursion depth equals target.
  • Unreachable target with huge intermediates: nums = [2, 4, 6, 8, 10], target = 999 returns 0 even though the counts for even sums overflow 64 bits.
  • Single large number: nums = [1000], target = 1000 returns 1.

Common Mistakes

  • Swapping the two loops. That computes the number of combinations (Coin Change II), not ordered sequences, and gives 3 instead of 5 for Example 1.
  • Using signed int in C++. Signed overflow is undefined behavior; use unsigned int or guard the additions.
  • Using a plain + on JavaScript numbers. Intermediate counts pass 2^53, lose precision, and dp[target] can come out wrong. Reduce modulo 2^32 (>>> 0).
  • Using -1 as the “not computed” marker in Java, C# or Go when counts wrap. A wrapped value can be negative and even exactly -1; keep a separate seen array (the JavaScript version is safe because its values stay in [0, 2^32)).
  • Forgetting the recursion limit in Python for target near 1000 with a small number in nums.

Interview Tips

  • Clarify early that order matters; Example 1 shows (1,1,2), (1,2,1) and (2,1,1) as three different answers.
  • Start from the recursive definition, point out the overlapping subproblems, then add memoization, then convert to bottom-up.
  • Raise the overflow question yourself. Explaining why wraparound gives the exact answer, or why you skip additions above INT_MAX, is a strong signal.
  • Contrast this with Coin Change II; interviewers often ask how to change the code to count combinations instead.

Follow-up Questions

  • What if nums could contain negative numbers? The count can become infinite: with 1 and -1 you can insert (1, -1) pairs forever. You would need a limit on sequence length, and the DP would need that length as an extra dimension.
  • How would you count unordered combinations? Put the loop over nums outside and the loop over sums inside, exactly as in Coin Change II.
  • How would you list the sequences rather than count them? Use backtracking, as in Combination Sum, but allow every number at every position. The output itself can be exponential in size.
  • What if each number could be used at most once? The problem becomes counting ordered subsets. Count unordered subsets by size with a 0/1 knapsack over (sum, count), then multiply the count for each size k by k! to get the ordered arrangements.