227. Combination Sum IV
🔗 LeetCode Problem: 377. Combination Sum IV
📊 Difficulty: Medium
🏷️ Topics: Dynamic Programming, Array, DP - Subsequences
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 in a 32-bit integer.
Example 1:
Input: nums = [1,2,3], target = 4
Output: 7
Explanation:
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.
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
Follow up: What if negative numbers are allowed in the given array? How does it change the problem? What limitation we need to add to the question to allow negative numbers?
🌳 Visual Understanding - Using nums = [1, 2, 3], target = 4
The Problem We're Solving:
Given: nums = [1, 2, 3], target = 4
Goal: Count how many ways to sum to 4 using these numbers
Numbers available (infinite supply):
1 - unlimited
2 - unlimited
3 - unlimited
Question: How many DIFFERENT SEQUENCES sum to 4? 🤔
CRITICAL: Order matters!
[1, 3] is DIFFERENT from [3, 1]
Both sum to 4, but count as 2 different combinations!
Finding All Combinations for target = 4:
Target: 4
Combination 1: [1, 1, 1, 1]
━━━━━━━━━━━━━━━━━━━━━━━━━━━
1 + 1 + 1 + 1 = 4 ✓
Combination 2: [1, 1, 2]
━━━━━━━━━━━━━━━━━━━━━━━━━━━
1 + 1 + 2 = 4 ✓
Combination 3: [1, 2, 1]
━━━━━━━━━━━━━━━━━━━━━━━━━━━
1 + 2 + 1 = 4 ✓
Different order from [1, 1, 2]!
Combination 4: [1, 3]
━━━━━━━━━━━━━━━━━━━━━━━━━━━
1 + 3 = 4 ✓
Combination 5: [2, 1, 1]
━━━━━━━━━━━━━━━━━━━━━━━━━━━
2 + 1 + 1 = 4 ✓
Different from [1, 1, 2] and [1, 2, 1]!
Combination 6: [2, 2]
━━━━━━━━━━━━━━━━━━━━━━━━━━━
2 + 2 = 4 ✓
Combination 7: [3, 1]
━━━━━━━━━━━━━━━━━━━━━━━━━━━
3 + 1 = 4 ✓
Different order from [1, 3]!
Total: 7 different combinations ✓
Answer: 7
Why ORDER MATTERS (This is KEY!):
CRITICAL UNDERSTANDING:
This problem counts PERMUTATIONS, not combinations!
Compare:
[1, 3] vs [3, 1]
In regular combinations: These are SAME (just {1, 3})
In this problem: These are DIFFERENT!
[1, 3] → use 1 first, then 3
[3, 1] → use 3 first, then 1
This is like asking:
"How many ways to climb 4 stairs using steps of 1, 2, or 3?"
Step 1 then Step 3: 1→3 (total 4)
Step 3 then Step 1: 3→1 (total 4)
Different paths! Both count! 🔑
This makes the problem HARDER than regular Coin Change!
Comparison with Coin Change:
COIN CHANGE (Problem 226):
Question: "Minimum COINS to make target"
Order: Doesn't matter
Example: [1, 3] and [3, 1] are SAME
Count: {1, 3} counts as 1 way
COMBINATION SUM IV (This Problem):
Question: "Count WAYS to make target"
Order: MATTERS!
Example: [1, 3] and [3, 1] are DIFFERENT
Count: [1, 3] and [3, 1] count as 2 ways
Same structure, different question! 🎯
🧠 The AHA Moment - Why This Problem Is Special
What Makes This Different?
COIN CHANGE:
dp[i] = minimum coins to make i
Order doesn't matter
COMBINATION SUM IV:
dp[i] = number of ways to make i
Order MATTERS!
Key difference: We're COUNTING, not MINIMIZING!
The Key Insight - Count All Sequences!
To make target, we can use ANY number from nums
If we use number num:
- We've built one step of the sequence
- Need to make (target - num) with remaining numbers
- Remaining has ??? ways (we need to count!)
- Total ways using num: (ways for target - num)
Try ALL numbers:
For num 1: ways(target - 1)
For num 2: ways(target - 2)
For num 3: ways(target - 3)
...
ADD them all up! (not minimize!)
dp[target] = ways(target - 1) + ways(target - 2) + ways(target - 3) + ...
This is the DP insight! 🔑
Building Intuition with Small Example:
nums = [1, 2], target = 3
Ways to make 3:
Option 1: Use 1 first
3 = 1 + (remaining 2)
Ways to make 2? → 2 ways: [1,1] and [2]
Sequences: [1,1,1] and [1,2]
Total: 2 ways
Option 2: Use 2 first
3 = 2 + (remaining 1)
Ways to make 1? → 1 way: [1]
Sequences: [2,1]
Total: 1 way
Add them: 2 + 1 = 3 total ways!
Verify:
[1, 1, 1] ✓
[1, 2] ✓
[2, 1] ✓
All 3 sequences are different! Count = 3 ✓
🔴 Approach 1: Brute Force (Try All Sequences)
📐 Function Definition
Function Signature:
int combinationSum4(int[] nums, int target)
What it represents:
Input Parameter nums:
- Array of distinct positive integers
- Each number can be used unlimited times
- Example: nums = [1, 2, 3]
Input Parameter target:
- Target sum to reach
- Example: target = 4
Return Value (int): - Number of different sequences that sum to target - Order matters! [1,3] ≠ [3,1] - Example: 7
Purpose: - Try all possible sequences - For each num, use it and recursively count remaining - Add up all the ways - Return total count
Key Understanding:
For nums = [1, 2, 3], target = 4:
Use 1: count(4-1=3) ways
Use 2: count(4-2=2) ways
Use 3: count(4-3=1) ways
For each choice, recursively count remaining!
ADD all the ways together!
💡 Intuition
The simplest idea: Try using each number, recursively count remaining!
Think of it like climbing stairs:
Target: Reach step 4
Allowed steps: 1, 2, or 3
From step 4, how did we get here?
- Took 1-step from step 3
- Took 2-step from step 2
- Took 3-step from step 1
Ways to reach step 4:
= ways to reach step 3
+ ways to reach step 2
+ ways to reach step 1
Recursive structure!
Each previous step has its own count of ways
Add them all up! 🎯
📝 Implementation
class Solution {
public int combinationSum4(int[] nums, int target) {
return helper(nums, target);
}
private int helper(int[] nums, int target) {
// Base case: target is 0, found one way!
if (target == 0) return 1;
// Base case: target is negative, no way
if (target < 0) return 0;
int totalWays = 0;
// Try each number
for (int num : nums) {
// Use this number, recursively count remaining
totalWays += helper(nums, target - num);
}
return totalWays;
}
}
🔍 Detailed Dry Run: nums = [1, 2, 3], target = 4
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RECURSIVE TREE (Partial - showing main paths)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
helper(nums, 4)
│
├─ Use 1: helper(nums, 3)
│ ├─ Use 1: helper(nums, 2)
│ │ ├─ Use 1: helper(nums, 1)
│ │ │ ├─ Use 1: helper(nums, 0)
│ │ │ │ return 1 ✓ → sequence [1,1,1,1]
│ │ │ └─ Total: 1
│ │ ├─ Use 2: helper(nums, 0)
│ │ │ return 1 ✓ → sequence [1,1,2]
│ │ └─ Total: 1 + 1 = 2
│ │
│ ├─ Use 2: helper(nums, 1)
│ │ ├─ Use 1: helper(nums, 0)
│ │ │ return 1 ✓ → sequence [1,2,1]
│ │ └─ Total: 1
│ │
│ ├─ Use 3: helper(nums, 0)
│ │ return 1 ✓ → sequence [1,3]
│ │
│ └─ Total: 2 + 1 + 1 = 4
│
├─ Use 2: helper(nums, 2)
│ ├─ Use 1: helper(nums, 1)
│ │ ├─ Use 1: helper(nums, 0)
│ │ │ return 1 ✓ → sequence [2,1,1]
│ │ └─ Total: 1
│ │
│ ├─ Use 2: helper(nums, 0)
│ │ return 1 ✓ → sequence [2,2]
│ │
│ └─ Total: 1 + 1 = 2
│
├─ Use 3: helper(nums, 1)
│ ├─ Use 1: helper(nums, 0)
│ │ return 1 ✓ → sequence [3,1]
│ │
│ └─ Total: 1
│
└─ Total: 4 + 2 + 1 = 7
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
FINAL RESULT: 7 ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
All 7 sequences found:
[1, 1, 1, 1]
[1, 1, 2]
[1, 2, 1]
[1, 3]
[2, 1, 1]
[2, 2]
[3, 1]
Why This Is Slow:
Notice the recursion tree:
helper(3) is called MULTIPLE times!
helper(2) is called MULTIPLE times!
helper(1) is called MULTIPLE times!
Lots of repeated work! This is the problem!
For target = 100, the tree would be GIGANTIC!
Many overlapping subproblems being counted over and over!
This is why brute force is TOO SLOW! ❌
📊 Complexity Analysis
Time Complexity: Exponential O(n^t)
n = number of elements in nums
t = target
At each level, we branch into n choices
Maximum depth is t (worst case using all 1's)
Total: n^t ≈ exponential
For target = 100, nums = [1,2,3]:
3^100 = astronomical!
WAY TOO SLOW! ❌
Space Complexity: O(t)
Recursion stack depth
In worst case (all 1's), depth = t
Why This Is Slow:
❌ Tries every possible sequence
❌ Repeats same subproblems many times
❌ Exponential time complexity
✅ But correct and easy to understand!
We need to CACHE the results! → Memoization!
🟡 Approach 2: Memoization (Top-Down DP)
📐 Function Definition
Function Signature:
int combinationSum4(int[] nums, int target)
What it represents:
Variables we track:
- memo[i] = Number of ways to make target i
- If memo[i] is computed, reuse it!
- If not computed, compute and cache it!
Purpose: - Same recursive logic as brute force - But CACHE results to avoid recomputation - Each subproblem solved only ONCE!
Key Understanding:
Brute force calls helper(3) many times
Memoization calls helper(3) ONCE, caches result
Example:
First time helper(3) called:
- Compute answer (4 ways)
- Store in memo[3] = 4
Next time helper(3) called:
- Check memo[3]
- Found! Return 4 immediately
- No recomputation! ✓
This saves MASSIVE amounts of work!
💡 Intuition
The smart idea: Remember what we've already counted!
Think of it like counting stairs:
WITHOUT memoization (brute force):
Question: "How many ways to reach step 3?"
You: *count all paths from scratch*
Later, same question: "How many ways to reach step 3?"
You: *count all paths from scratch AGAIN* ❌
WITH memoization:
Question: "How many ways to reach step 3?"
You: *count all paths from scratch*
You: *write in notebook: "Step 3 = 4 ways"*
Later, same question: "How many ways to reach step 3?"
You: *check notebook*
You: "It's 4 ways!" ✓
You: *instant answer, no recounting!*
The notebook is the memo array!
📝 Implementation
class Solution {
private int[] memo;
public int combinationSum4(int[] nums, int target) {
memo = new int[target + 1];
Arrays.fill(memo, -1); // -1 means not computed yet
return helper(nums, target);
}
private int helper(int[] nums, int target) {
// Base case: target is 0, found one way!
if (target == 0) return 1;
// Base case: target is negative, no way
if (target < 0) return 0;
// Check memo (our notebook!)
if (memo[target] != -1) {
return memo[target];
}
int totalWays = 0;
// Try each number
for (int num : nums) {
// Recursive call (might hit memo!)
totalWays += helper(nums, target - num);
}
// Save to memo before returning!
memo[target] = totalWays;
return totalWays;
}
}
🔍 Detailed Dry Run: nums = [1, 2, 3], target = 4
memo = [-1, -1, -1, -1, -1]
0 1 2 3 4
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
CALL: helper(nums, 4)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
target = 4
memo[4] = -1 (not computed yet)
totalWays = 0
Try num 1: helper(nums, 3)
┌─ CALL: helper(nums, 3)
│ target = 3
│ memo[3] = -1 (not computed yet)
│ totalWays = 0
│
│ Try num 1: helper(nums, 2)
│ ┌─ CALL: helper(nums, 2)
│ │ target = 2
│ │ memo[2] = -1
│ │ totalWays = 0
│ │
│ │ Try num 1: helper(nums, 1)
│ │ ┌─ CALL: helper(nums, 1)
│ │ │ target = 1
│ │ │ memo[1] = -1
│ │ │ totalWays = 0
│ │ │
│ │ │ Try num 1: helper(nums, 0)
│ │ │ return 1 (base case)
│ │ │ totalWays = 0 + 1 = 1
│ │ │
│ │ │ Try num 2: helper(nums, -1)
│ │ │ return 0 (negative)
│ │ │ totalWays = 1 + 0 = 1
│ │ │
│ │ │ Try num 3: helper(nums, -2)
│ │ │ return 0 (negative)
│ │ │ totalWays = 1 + 0 = 1
│ │ │
│ │ │ memo[1] = 1 ✓
│ │ └─ return 1
│ │
│ │ totalWays = 0 + 1 = 1
│ │
│ │ Try num 2: helper(nums, 0)
│ │ return 1 (base case)
│ │ totalWays = 1 + 1 = 2
│ │
│ │ Try num 3: helper(nums, -1)
│ │ return 0 (negative)
│ │ totalWays = 2 + 0 = 2
│ │
│ │ memo[2] = 2 ✓
│ └─ return 2
│
│ totalWays = 0 + 2 = 2
│
│ Try num 2: helper(nums, 1)
│ target = 1
│ memo[1] = 1 ← FOUND IN MEMO! ✓
│ return 1 (instant, no recursion!)
│
│ totalWays = 2 + 1 = 3
│
│ Try num 3: helper(nums, 0)
│ return 1 (base case)
│ totalWays = 3 + 1 = 4
│
│ memo[3] = 4 ✓
└─ return 4
totalWays = 0 + 4 = 4
Try num 2: helper(nums, 2)
target = 2
memo[2] = 2 ← FOUND IN MEMO! ✓
return 2 (instant!)
totalWays = 4 + 2 = 6
Try num 3: helper(nums, 1)
target = 1
memo[1] = 1 ← FOUND IN MEMO! ✓
return 1 (instant!)
totalWays = 6 + 1 = 7
memo[4] = 7 ✓
return 7
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
FINAL memo state:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
memo = [1, 1, 2, 4, 7]
0 1 2 3 4
Verification:
memo[0] = 1 (base: one way to make 0)
memo[1] = 1 (only [1])
memo[2] = 2 ([1,1], [2])
memo[3] = 4 ([1,1,1], [1,2], [2,1], [3])
memo[4] = 7 (all 7 sequences!) ✓
Each value computed ONCE and cached! ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: 7 ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Notice: helper(1), helper(2), helper(3)
all called MULTIPLE times
First call: computed and cached
Later calls: returned from memo instantly!
This is the power of memoization!
Why This Works:
KEY INSIGHT:
Each unique target is solved ONCE
Result is cached in memo[target]
Future calls return cached result instantly
Comparison:
Brute force: helper(3) computed multiple times
Memoization: helper(3) computed ONCE, cached
This transforms exponential → linear time!
📊 Complexity Analysis
Time Complexity: O(t × n)
t = target
n = number of elements in nums
t unique subproblems (0 to target)
Each subproblem tries n numbers
Each subproblem solved ONCE (cached!)
Total: t × n
For target = 1000, nums = [1,2,3]:
1000 × 3 = 3,000 operations
MUCH better than exponential! ✓
Space Complexity: O(t)
Memo array: O(t)
Recursion stack: O(t) in worst case
Total: O(t)
🟢 Approach 3: Bottom-Up DP (Iterative)
📐 Function Definition
Function Signature:
int combinationSum4(int[] nums, int target)
What it represents:
DP Array:
- dp[i] = Number of ways to make target i
- Build from dp[0], dp[1], ..., up to dp[target]
- Each value uses previous values!
Purpose: - Compute answers for 0, 1, 2, ..., target in order - For each i, try all numbers in nums - Use previously computed dp values!
Key Understanding:
Bottom-up builds from smallest to largest:
dp[0] = 1 (base case: one way to make 0 - empty sequence)
dp[1]: Try all nums, add up ways from (1 - num)
dp[2]: Try all nums, add up ways from (2 - num)
dp[3]: Try all nums, add up ways from (3 - num)
...
dp[target]: Try all nums, add up ways from (target - num)
Build up the solution incrementally!
💡 Intuition
The systematic idea: Build answers from bottom up, like climbing stairs!
Think of it like counting paths on stairs:
TOP-DOWN (Memoization):
Start at top stair (target)
Work backwards to ground (0)
Cache counts as you go
BOTTOM-UP (This approach):
Start at ground (0)
Work upwards to top (target)
Build on previous counts
Like recording how many paths to each stair:
Ground (0): 1 way (already there)
Stair 1: use dp[0] → 1 way
Stair 2: use dp[1], dp[0] → 2 ways
Stair 3: use dp[2], dp[1], dp[0] → 4 ways
Stair 4: use dp[3], dp[2], dp[1] → 7 ways
Each stair uses stairs below it!
📝 Implementation
class Solution {
public int combinationSum4(int[] nums, int target) {
// dp[i] = number of ways to make target i
int[] dp = new int[target + 1];
// Base case: one way to make 0 (empty sequence)
dp[0] = 1;
// Build up from 1 to target
for (int i = 1; i <= target; i++) {
// Try each number in nums
for (int num : nums) {
// Can we use this number?
if (i >= num) {
// ═══════════════════════════════════════════════════
// BACKWARD DP: Add ways from previous value
// ═══════════════════════════════════════════════════
// To make i, use num once
// Then ways to make i - num
// Add those ways to dp[i]
dp[i] += dp[i - num];
}
}
}
return dp[target];
}
}
🔍 Detailed Dry Run: nums = [1, 2, 3], target = 4
Initial state:
dp = [1, 0, 0, 0, 0]
0 1 2 3 4
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
BUILD DP TABLE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Iteration: i = 1
━━━━━━━━━━━━━━━━━━━━
nums: [1, 2, 3]
dp[1] = 0 (initially)
Try num 1:
i >= 1? YES ✓
dp[1] += dp[1 - 1]
dp[1] += dp[0]
dp[1] += 1
dp[1] = 0 + 1 = 1 ✓
(Sequence: [1])
Try num 2:
i >= 2? NO (1 < 2)
Skip
Try num 3:
i >= 3? NO (1 < 3)
Skip
dp[1] = 1
Iteration: i = 2
━━━━━━━━━━━━━━━━━━━━
dp[2] = 0 (initially)
Try num 1:
i >= 1? YES ✓
dp[2] += dp[2 - 1]
dp[2] += dp[1]
dp[2] += 1
dp[2] = 0 + 1 = 1
(Sequences so far: [1, 1])
Try num 2:
i >= 2? YES ✓
dp[2] += dp[2 - 2]
dp[2] += dp[0]
dp[2] += 1
dp[2] = 1 + 1 = 2 ✓
(Added sequence: [2])
Try num 3:
i >= 3? NO
Skip
dp[2] = 2
(Sequences: [1,1], [2])
Iteration: i = 3
━━━━━━━━━━━━━━━━━━━━
dp[3] = 0 (initially)
Try num 1:
i >= 1? YES ✓
dp[3] += dp[3 - 1]
dp[3] += dp[2]
dp[3] += 2
dp[3] = 0 + 2 = 2
(Sequences from dp[2]:
[1,1] → [1,1,1]
[2] → [2,1])
Try num 2:
i >= 2? YES ✓
dp[3] += dp[3 - 2]
dp[3] += dp[1]
dp[3] += 1
dp[3] = 2 + 1 = 3
(Sequences from dp[1]:
[1] → [1,2])
Try num 3:
i >= 3? YES ✓
dp[3] += dp[3 - 3]
dp[3] += dp[0]
dp[3] += 1
dp[3] = 3 + 1 = 4 ✓
(Sequences from dp[0]:
[] → [3])
dp[3] = 4
(Sequences: [1,1,1], [1,2], [2,1], [3])
Iteration: i = 4 - FINAL
━━━━━━━━━━━━━━━━━━━━
dp[4] = 0 (initially)
Try num 1:
i >= 1? YES ✓
dp[4] += dp[4 - 1]
dp[4] += dp[3]
dp[4] += 4
dp[4] = 0 + 4 = 4
(Sequences from dp[3]:
[1,1,1] → [1,1,1,1]
[1,2] → [1,2,1]
[2,1] → [2,1,1]
[3] → [3,1])
Try num 2:
i >= 2? YES ✓
dp[4] += dp[4 - 2]
dp[4] += dp[2]
dp[4] += 2
dp[4] = 4 + 2 = 6
(Sequences from dp[2]:
[1,1] → [1,1,2]
[2] → [2,2])
Try num 3:
i >= 3? YES ✓
dp[4] += dp[4 - 3]
dp[4] += dp[1]
dp[4] += 1
dp[4] = 6 + 1 = 7 ✓
(Sequences from dp[1]:
[1] → [1,3])
dp[4] = 7
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
FINAL DP ARRAY:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
dp = [1, 1, 2, 4, 7]
0 1 2 3 4
Verification:
dp[0] = 1 (empty sequence)
dp[1] = 1 ([1])
dp[2] = 2 ([1,1], [2])
dp[3] = 4 ([1,1,1], [1,2], [2,1], [3])
dp[4] = 7 (all 7 sequences!) ✓
All 7 sequences:
[1, 1, 1, 1]
[1, 1, 2]
[1, 2, 1]
[1, 3]
[2, 1, 1]
[2, 2]
[3, 1]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
ANSWER: 7 ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Why This Works - Visual Understanding:
Think of it like Fibonacci:
Fibonacci:
fib[0] = 0
fib[1] = 1
fib[n] = fib[n-1] + fib[n-2]
Compute fib[2], fib[3], ..., in order
Each uses previous values!
Combination Sum IV:
dp[0] = 1
dp[i] = sum of dp[i - num] for all nums
Compute dp[1], dp[2], ..., in order
Each uses previous values!
SAME PATTERN - Build from bottom up! 🎯
But here we ADD instead of just looking at neighbors!
📊 Complexity Analysis
Time Complexity: O(t × n)
t = target
n = number of elements in nums
Outer loop: t iterations (1 to target)
Inner loop: n numbers to try
Total: t × n
For target = 1000, nums = 3:
1000 × 3 = 3,000 operations
Very manageable! ✓
Space Complexity: O(t)
DP array of size target + 1
No recursion stack needed
Total: O(t)
📊 Approach Comparison
┌──────────────────────────────────────────────────────────────┐
│ COMBINATION SUM IV - APPROACH COMPARISON │
├──────────────┬───────────┬───────────┬────────────┬──────────┤
│ Approach │ Time │ Space │ Clarity │Interview │
├──────────────┼───────────┼───────────┼────────────┼──────────┤
│ Brute Force │ Exp │ O(t) │ High │ Start │
│ Memoization │ O(t×n) │ O(t) │ Good │ Good │
│ Bottom-Up DP │ O(t×n) │ O(t) │ Best ✓ │ Best ✓ │
└──────────────┴───────────┴───────────┴────────────┴──────────┘
t = target, n = number of elements
For interviews: Show progression from brute force to DP!
💻 Complete Working Code
class Solution {
public int combinationSum4(int[] nums, int target) {
return dp(nums, target);
}
// Approach 3: Bottom-Up DP - O(t×n) time, O(t) space
private int dp(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1; // Base case
for (int i = 1; i <= target; i++) {
for (int num : nums) {
if (i >= num) {
dp[i] += dp[i - num];
}
}
}
return dp[target];
}
// Approach 2: Memoization - O(t×n) time, O(t) space
private int[] memo;
private int memoization(int[] nums, int target) {
memo = new int[target + 1];
Arrays.fill(memo, -1); // -1 = not computed
return helperMemo(nums, target);
}
private int helperMemo(int[] nums, int target) {
if (target == 0) return 1;
if (target < 0) return 0;
if (memo[target] != -1) return memo[target];
int totalWays = 0;
for (int num : nums) {
totalWays += helperMemo(nums, target - num);
}
memo[target] = totalWays;
return totalWays;
}
// Approach 1: Brute Force - Exponential time
private int bruteForce(int[] nums, int target) {
return helperBrute(nums, target);
}
private int helperBrute(int[] nums, int target) {
if (target == 0) return 1;
if (target < 0) return 0;
int totalWays = 0;
for (int num : nums) {
totalWays += helperBrute(nums, target - num);
}
return totalWays;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.combinationSum4(new int[] { 1, 2, 3 }, 4) == 7);
System.out.println(s.combinationSum4(new int[] { 9 }, 3) == 0);
}
}
🔑 Key Insights
Order MATTERS:
CRITICAL DIFFERENCE from Coin Change!
Coin Change: [1, 3] same as [3, 1]
→ Count as 1 way
This Problem: [1, 3] different from [3, 1]
→ Count as 2 ways
We're counting SEQUENCES, not COMBINATIONS!
This is like counting permutations! 🔑
Pattern Recognition:
This is PERMUTATIONS with repetition!
Similar problems:
- Climbing Stairs (different step sizes)
- Dice Throws (count ways to sum)
- Ways to Decode (with constraints)
All count sequences where order matters!
Why DP Works:
For each target i, try using every number:
dp[i] = sum of dp[i - num] for all nums
Build from dp[0] to dp[target]
Each value uses previous values
ADD the ways (not minimize!)
Integer Overflow Warning:
Problem says answer fits in 32-bit integer
But intermediate calculations might overflow!
Safe practice:
Check for overflow before adding
Or use long if needed
🎪 Memory Aid
"Order MATTERS - different sequences!"
"ADD the ways from all choices!"
"Like Fibonacci but sum ALL previous!"
"Counting permutations with unlimited items!" ✨
⚠️ Common Mistakes
- ❌ Treating like Coin Change (order doesn't matter)
- ❌ Forgetting base case dp[0] = 1
- ❌ Not checking i >= num before accessing dp[i - num]
- ❌ Using min instead of adding (this counts, not minimizes!)
- ❌ Integer overflow (be careful with large targets!)
✅ Interview Talking Points
"This is different from Coin Change because ORDER MATTERS.
Key difference:
Coin Change: [1,3] same as [3,1] → 1 way
This problem: [1,3] vs [3,1] → 2 ways
We're counting SEQUENCES (permutations)
Not combinations!
DP Approach:
dp[i] = number of ways to make target i
Base case: dp[0] = 1 (empty sequence)
For each i from 1 to target:
Try every number in nums
dp[i] += dp[i - num]
We ADD the ways (not minimize like Coin Change)
This counts all different sequences!
Complexity: O(t×n) time, O(t) space
where t = target, n = number of elements
Optimal solution!"
📝 Quick Revision Notes
⚡ Quick Implementation
import java.util.Arrays;
public class Solution {
public int combinationSum4(int[] nums, int k) {
// return recursive(nums, k);
// int[] memo = new int[k + 1];
// Arrays.fill(memo, -1);
// return topDown(nums, k, memo);
return bottomUp(nums, k);
}
private int bottomUp(int[] nums, int k) {
int[] dp = new int[k + 1];
// base case
dp[0] = 1;
for (int i = 1; i <= k; i++) {
for (int num : nums) {
if (i - num < 0) {
continue;
}
dp[i] = dp[i] + dp[i - num];
}
}
return dp[k];
}
private int topDown(int[] nums, int k, int[] memo) {
if (k == 0) {
return 1;
}
if (k < 0) {
return 0;
}
if (memo[k] != -1) {
return memo[k];
}
int count = 0;
for (int num : nums) {
count += topDown(nums, k - num, memo);
}
return memo[k] = count;
}
private int recursive(int[] nums, int k) {
// step 3: base case 1
if (k == 0) {
return 1;
}
// step 3: base case 2
if (k < 0) {
return 0;
}
// step 1
int count = 0;
for (int num : nums) {
count += recursive(nums, k - num);
}
// step 2
return count;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.combinationSum4(new int[] { 1, 2, 3 }, 4) == 7);
System.out.println(s.combinationSum4(new int[] { 9 }, 3) == 0);
}
}
🎉 Congratulations!
You've mastered Combination Sum IV - counting sequences with DP!
What You Learned:
✅ Order matters - Different from Coin Change
✅ Count sequences - Permutations, not combinations
✅ Brute force - Try all sequences recursively
✅ Memoization - Cache counts to avoid recomputation
✅ Bottom-up DP - Build from 0 to target
✅ Add, don't minimize - Count all ways
This is a beautiful variation of Unbounded Knapsack! 🚀✨