Combination Sum IV

medium
Dynamic ProgrammingArrayDynamic Programming

Given an array of distinct positive integers nums and a target integer target, return the number of possible combinations that add up to target. Different sequences that sum to the same target are counted as distinct combinations (order matters).

Examples

Example 1

  • Input: nums = [1,2,3], target = 4
  • Output: 7
  • Explanation: The possible combinations are: (1,1,1,1), (1,1,2), (1,2,1), (1,3), (2,1,1), (2,2), (3,1).

Example 2

  • Input: nums = [9], target = 3
  • Output: 0
  • Explanation: No combination of [9] can sum to 3.

Constraints

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 1000
  • All the elements of nums are unique.
  • 1 <= target <= 1000

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Recursion (Brute Force)

Intuition

Since order matters, this is a permutation-style counting problem. For each recursive call with a remaining target, we try every number in nums that does not exceed the target. If the target becomes zero, we have found one valid combination. The overlapping subproblems make this exponential without memoization.

Algorithm

  1. If `target == 0`, return `1` (one valid combination found).
  2. Initialize `count = 0`.
  3. For each number in `nums`, if `num <= target`, recursively count combinations for `target - num`.
  4. Return the total count.
TimeO(n^target) where n is the length of numsSpaceO(target) for the recursion stack

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        if (target == 0) return 1;
        int count = 0;
        for (int num : nums) {
            if (num <= target) {
                count += combinationSum4(nums, target - num);
            }
        }
        return count;
    }
};
Java 21
class Solution {
    public int combinationSum4(int[] nums, int target) {
        if (target == 0) return 1;
        int count = 0;
        for (int num : nums) {
            if (num <= target) {
                count += combinationSum4(nums, target - num);
            }
        }
        return count;
    }
}
Python 3.12
from typing import List

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        if target == 0:
            return 1
        count = 0
        for num in nums:
            if num <= target:
                count += self.combinationSum4(nums, target - num)
        return count
Go 1.26
func combinationSum4(nums []int, target int) int {
    if target == 0 {
        return 1
    }
    count := 0
    for _, num := range nums {
        if num <= target {
            count += combinationSum4(nums, target-num)
        }
    }
    return count
}
Approach 2

Dynamic Programming (Bottom-Up)

Intuition

Build a table dp where dp[i] is the number of ordered combinations that sum to i. For each amount from 1 to target, try every number in nums: if it does not exceed the current amount, add dp[i - num] to dp[i]. This counts all orderings because we iterate over nums for every sub-target.

Algorithm

  1. Create array `dp` of size `target + 1`, with `dp[0] = 1`.
  2. For each `i` from 1 to `target`:
  3. Return `dp[target]`.
TimeO(target * n)SpaceO(target)

Code (C++ · Java · Python · Go)

C++17
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 (num <= i) {
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp[target];
    }
};
Java 21
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 (num <= i) {
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp[target];
    }
}
Python 3.12
from typing import List

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 num <= i:
                    dp[i] += dp[i - num]
        return dp[target]
Go 1.26
func combinationSum4(nums []int, target int) int {
    dp := make([]int, target+1)
    dp[0] = 1
    for i := 1; i <= target; i++ {
        for _, num := range nums {
            if num <= i {
                dp[i] += dp[i-num]
            }
        }
    }
    return dp[target]
}

Frequently asked questions

What is the optimal time complexity of Combination Sum IV?

The most efficient approach in this guide ("Dynamic Programming (Bottom-Up)") runs in O(target * n) time and uses O(target) extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Combination Sum IV use?

Combination Sum IV is a medium-level Dynamic Programming problem involving Array, Dynamic Programming. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Combination Sum IV be solved without extra space?

The most space-efficient approach in this guide uses O(target) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(target) for the recursion stack, while the optimized version uses O(target).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Original problem: leetcode.com

Loading editor...
Input
nums=
[1,2,3]
target=
4
Expected Output
7