Log inSign up
mediumLeetCodeNot Started

Combination Sum IV

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on LeetCode
Lesson

Problem Statement

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

The test cases are generated so that the answer can fit into a 32-bit integer.

Note: In this problem, different sequences of numbers are counted as distinct combinations (i.e. permutations matter: (1, 2) and (2, 1) are considered distinct).

### 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) Total = 7.

### Example 2 - Input: nums = [9], target = 3 - Output: 0

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Distinguish between DP loop order for combinations vs permutations.
  • Derive the generalized Fibonacci-style recurrence: dp[t] = sum(dp[t - num]).
  • Handle potential 32-bit arithmetic overflow during intermediate summation.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Finding number of sequences summing to target.
  • Order of elements in sequence matters (e.g. (1, 2) != (2, 1)).
  • Generalization of Climbing Stairs with arbitrary step sizes.

Algorithmic Decision Tree:

  • Permutations matter -> Outer loop = Target, Inner loop = Numbers.
  • Combinations (order doesn't matter) -> Outer loop = Numbers, Inner loop = Target.

Connected Patterns:

Climbing StairsCoin Change IIDecode Ways

1. Recursive DFS Permutation Search

Intuition

At each step, subtract each candidate number from remaining target and sum all valid paths.

Algorithm

  1. Define dfs(rem).
  2. If rem == 0, return 1.
  3. If rem < 0, return 0.
  4. Initialize total = 0.
  5. For each x in nums: total += dfs(rem - x).
  6. Return total.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int dfs(int rem, const vector<int>& nums) {
7 if (rem == 0) return 1;
8 if (rem < 0) return 0;
9 int count = 0;
10 for (int x : nums) {
11 count += dfs(rem - x, nums);
12 }
13 return count;
14}
15
16int combinationSum4Rec(vector<int>& nums, int target) {
17 return dfs(target, nums);
18}
19
20int main() {
21 vector<int> nums = {1, 2, 3};
22 int target = 4;
23 cout << "Combinations (Recursive): " << combinationSum4Rec(nums, target) << endl;
24 return 0;
25}

Time & Space Complexity

  • Time complexity: O(N^target) where N = nums.length
  • Space complexity: O(target) recursion stack

2. Top-Down Memoized DP

Intuition

Store results for each sub-target in a memo array of size target + 1.

Algorithm

  1. Create memo array of size target + 1 filled with -1.
  2. memo[0] = 1.
  3. Define solve(rem): if rem < 0 return 0; if memo[rem] != -1 return memo[rem].
  4. Compute sum(solve(rem - x)) for each x in nums.
  5. Save in memo[rem] and return.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int solveMemo(int rem, const vector<int>& nums, vector<int>& memo) {
7 if (rem == 0) return 1;
8 if (rem < 0) return 0;
9 if (memo[rem] != -1) return memo[rem];
10
11 int count = 0;
12 for (int x : nums) {
13 count += solveMemo(rem - x, nums, memo);
14 }
15 return memo[rem] = count;
16}
17
18int combinationSum4Memo(vector<int>& nums, int target) {
19 vector<int> memo(target + 1, -1);
20 return solveMemo(target, nums, memo);
21}
22
23int main() {
24 vector<int> nums = {1, 2, 3};
25 int target = 4;
26 cout << "Combinations (Memoized): " << combinationSum4Memo(nums, target) << endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(target * nums.length)
  • Space complexity: O(target) memo table and call stack

3. Bottom-Up 1D DP Tabulation

Intuition

Build array dp of size target + 1. Outer loop iterates over amounts from 1 to target; inner loop sums dp[t - num].

Algorithm

  1. Create array dp of size target + 1 filled with 0.
  2. dp[0] = 1.
  3. For t = 1 to target:
  4. For each num in nums:
  5. If num <= t:
  6. dp[t] += dp[t - num].
  7. Return dp[target].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int combinationSum4Optimal(vector<int>& nums, int target) {
7 vector<unsigned int> dp(target + 1, 0);
8 dp[0] = 1;
9
10 for (int t = 1; t <= target; t++) {
11 for (int num : nums) {
12 if (num <= t) {
13 dp[t] += dp[t - num];
14 }
15 }
16 }
17 return dp[target];
18}
19
20int main() {
21 vector<int> nums = {1, 2, 3};
22 int target = 4;
23 cout << "Combinations (Optimal 1D DP): " << combinationSum4Optimal(nums, target) << endl;
24 return 0;
25}

Time & Space Complexity

  • Time complexity: O(target * nums.length)
  • Space complexity: O(target) auxiliary space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive DFSO(N^target)O(target)Exhaustive branching over all numbers.Recomputes same remainders
2.Top-Down Memoized DPO(target * N)O(target)Cache intermediate remainders.Call stack
3.Bottom-Up 1D TabulationOptimalO(target * N)O(target)Target outer loop, numbers inner loop.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Looping over nums outside and target inside (this computes combinations as in Coin Change II, giving 4 instead of 7).

Pitfall 2:

Using signed 32-bit int in C++ without checking overflow for intermediate values.

Crucial Edge Cases to Validate:

  • target cannot be formed: Output is 0.
  • All nums greater than target: Output is 0.
  • nums contains 1: target can always be reached in at least 1 way.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explicitly acknowledge the naming confusion to your interviewer: 'Even though the title says combinations, the example shows that order matters, making this an ordered sequence/permutation problem equivalent to generalized climbing stairs.'

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does this problem ask for permutations despite being named 'Combination Sum IV'?

Back to DSA Sheet