Backtracking — Combination Sum IV
↗ LeetCode: Combination Sum IV · Medium · pattern chapter →
Asked atAmazonGoogleMeta
Count ordered sequences of nums summing to target. [1,2] and [2,1] are distinct.
Example 1 — nums=[1,2,3], target=4 → 7Example 2 — nums=[9], target=3 → 0
Constraints — 1 ≤ n ≤ 200. Brute recursion tries every ordered combination — at target=1000 with 4 nums that's 4^1000 = 10⁶⁰² ops. Bottom-up DP counting orderings is O(target·n) = 10³·200 = 2·10⁵ ops.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — Backtracking
Exponential. TLE.
Approach 2 — DP (coin-change permutations, canonical)
Insight. dp[t] = Σ dp[t - x] for x ∈ nums. Outer loop is target; inner is nums — this counts ordered sequences.
java
int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for (int t = 1; t <= target; t++)
for (int x : nums)
if (x <= t) dp[t] += dp[t - x];
return dp[target];
}Execution Trace
Step 1 / 3Initialize scan.
Contrast. Loop order swap counts unordered (see Coin Change II).
Trap — may overflow — problem guarantees fits in int; if unsure use long.
Complexity — Time O(target · n); Space O(target).
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Backtracking | exponential | O(target) | baseline |
| DP | O(target · n) | O(target) | canonical |
When to use which
- Ordered → outer target, inner nums.
- Unordered → outer nums, inner target.
- "Enumerate sequences" → backtracking, not DP.
AI Study CompanionBeta
Related problems
Was this page helpful?
📚 Related problems