Pattern this teaches:Backtracking Basics
Combination Sum
A medium Backtracking interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Backtracking
- Sheets
- 3
- Core for
- 0 roles
The problem
From a list of distinct positive numbers, find every group of numbers that adds up to target, where each number may be picked any number of times. Groups that differ only in order count as the same group; return each group once, in any order.
Example 1
- Input
- candidates = [2, 5, 6, 9], target = 9
- Output
- [[2, 2, 5], [9]]
- Why
- 2+2+5 reaches 9 with repeats allowed, and 9 alone works.
Example 2
- Input
- candidates = [3, 4, 7], target = 10
- Output
- [[3, 3, 4], [3, 7]]
- Why
- Two ways: 3+3+4 and 3+7.
Constraints
- 1 <= candidates.length <= 30
- 1 <= candidates[i] <= 200
- All elements of candidates are distinct
- 1 <= target <= 500
How to think about it
Updated 2026-09-29Unlimited reuse does not mean unrestricted ordering. Ordering causes duplicate permutations like [2, 3, 2] and [2, 2, 3]; freezing an index pointer and only allowing transitions to the current candidate or later candidates enforces a canonical non-decreasing choice order while preserving full freedom of repetition.
Approaches, worst first
Unconstrained branching with set deduplication
time O(n^(target / min)) · space O(target / min * n^(target / min))
Allow any candidate to be chosen at each recursive step, backtracking when sum exceeds target, then sorting paths to filter out permutations via a set. Blows up exponentially due to visiting all factorial orderings of identical multisets.
Forward index recursion
time O(n^(target / min)) · space O(target / min)
Recurse with an index parameter. From index i, branch on candidates[j] for j >= i, passing j (not j + 1) to allow reuse of the same number. Stops immediately when remaining target reaches zero or turns negative.
Sort and prune earlyWrite this one
time O(n^(target / min)) · space O(target / min)
Sort candidates ascending before searching. In the exploration loop, if candidates[j] exceeds the remaining target, break out immediately instead of continuing the loop. This truncates hopeless subtrees across all remaining larger numbers.
Where people lose marks · 3
- Passing i + 1 instead of i to the recursive call, which prevents candidates from being reused and misses valid combinations like [2, 2, 2, 2].
- Subtracting without breaking when candidates are unsorted. A break statement inside the loop only prunes correctly if candidates are sorted in ascending order.
- Using candidates[i] <= 0 logic or assuming zero is possible. Constraints state candidate values are at least 1, which guarantees recursion depth is strictly bounded.
The theory behind it
Backtracking — the ground this problem stands on. All Backtracking problems
What Backtracking is
Backtracking is an organized trial-and-error search through a maze of possibilities. You make a tentative choice, move forward to explore where that path leads, and if you hit a dead end or finish finding an answer, you back up and undo that choice. By cleaning up your changes before trying the next option, a single shared board or list is explored thoroughly without needing to clone full copies of your data at every turn.
When to reach for it
Reach for backtracking when a problem asks to generate all possible solutions, like all subsets, permutations, valid parentheses combinations, or word search paths on a board. Signals include puzzles with strict constraint rules, like placing eight non-attacking queens on a chessboard or solving a Sudoku grid. Whenever you must construct combinations step by step and abandon dead-end branches early before wasting time exploring impossible paths, use backtracking.
How the pattern works
Follow a three-step rhythm inside a loop: choose, explore, and unchoose. First, check if the current state satisfies your goal; if so, save a copy of it and return. Next, prune illegal moves immediately using constraint checks so unpromising branches are skipped. For each valid candidate, apply the move to your shared path or board, call the recursive function to explore deeper, and finally undo the move right after the call returns. Undoing restores the shared state so sibling choices start from a clean slate.
More Backtracking problems
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .