March 24
Combination Sum
How to use controlled backtracking to build unique combinations in canonical order.
Backtracking Intermediate 20 min TypeScript
Given an array of distinct integers candidates and an integer target, return all unique combinations where the chosen numbers sum to target.
You may use the same number from candidates as many times as you want.
In the SeniorPath playground:
- each combination must be in non-decreasing order
- the final list must follow the natural DFS order after sorting
candidatesin ascending order
Example:
Input: candidates = [2, 3, 6, 7], target = 7
Output: [[2, 2, 3], [7]]
What to notice before coding
- The problem asks for unique combinations, not different permutations of the same values.
- Reuse is allowed. After choosing a number, you may want to choose it again.
- The start index does two jobs at once: it avoids duplicates and decides whether the current number can still be reused.
Common mistakes
- restarting from index 0 on every recursive call and generating the same combination in different orders
- moving to `i + 1` right after choosing `candidates[i]` and accidentally forbidding reuse
Step 1 - Understand what "unique combination" means
The problem does not want every possible ordering.
If [2, 2, 3] already exists, then [2, 3, 2] and [3, 2, 2] are not new answers.
That changes the DFS shape a lot.
Step 2 - Write the most direct baseline
The natural baseline is:
- try each candidate
- keep the current path
- stop when the sum matches or passes the target
It works.
But if you can always choose any candidate again, you end up building the same combination in many orders.
Step 3 - Ask how to block those duplicate orders
The strong idea is imposing a canonical order.
Instead of letting the path jump back and forth between candidates, you decide:
- either use the current number and stay on the same index
- or advance to larger candidates
That means the path never goes backward.
Step 4 - Turn that into backtracking
The needed state is:
startIndex: where the loop is allowed to restartremaining: how much is left to reach the targetpath: the current combination
If remaining === 0, you found an answer.
If remaining < 0, that path is dead.
The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.
Starter code
export function combinationSum(candidates: number[], target: number): number[][] {
// your solution here
return []
}
Haven't solved it yet?
Viewing the solution now may reduce learning. It's worth trying a bit more.
Open the reference solution
Without JavaScript, the reference solution is shown inline instead of in a dialog.
Solution
Final complexity
Time: O(number of explored paths)
Space: O(target / min(candidates))
Solution 1 - Generate too many orders and deduplicate later
Good baseline because it makes the waste visible.
export function combinationSum(candidates: number[], target: number): number[][] {
const unique = new Set<string>()
function dfs(remaining: number, path: number[]) {
if (remaining === 0) {
unique.add([...path].sort((a, b) => a - b).join(","))
return
}
if (remaining < 0) {
return
}
for (const candidate of candidates) {
path.push(candidate)
dfs(remaining - candidate, path)
path.pop()
}
}
dfs(target, [])
return [...unique].map((entry) => entry.split(",").map(Number))
}It can work.
But it has an ugly flaw: it builds the same set of numbers in many orders and only cleans the mess at the end.
Solution 2 - Backtracking + DFS with an index to keep canonical order
Now the idea gets disciplined:
- sort
candidates - do DFS from a
startIndex - in the loop, only move forward
- when you choose
candidates[i], recurse with the sameiso reuse stays allowed
export function combinationSum(candidates: number[], target: number): number[][] {
const sorted = [...candidates].sort((a, b) => a - b)
const result: number[][] = []
const path: number[] = []
function dfs(startIndex: number, remaining: number) {
if (remaining === 0) {
result.push([...path])
return
}
for (let index = startIndex; index < sorted.length; index += 1) {
const candidate = sorted[index]
if (candidate > remaining) {
break
}
path.push(candidate)
dfs(index, remaining - candidate)
path.pop()
}
}
dfs(0, target)
return result
}The most important detail is here:
dfs(index, remaining - candidate)It is index, not index + 1.
That is what allows the same number to be used again.
If the problem banned reuse, then it would become index + 1.
What to say in the interview
A good short explanation would be:
The baseline tries candidates in any order and then has to deduplicate equal answers. The stronger version sorts the input and uses backtracking with a
startIndex. That keeps each combination in canonical order, avoids repeated permutations, and still allows reuse because the recursive call stays on the same index.
That shows four good signals:
- you understood why duplication appears
- you controlled order instead of cleaning it later
- you explained reuse correctly
- you tied the recursion parameter back to the rule of the problem
When this pattern shows up again
The same idea comes back when the problem asks you to:
- enumerate combinations
- choose items with reuse
- avoid duplicate answers caused by different orderings
- prune early when the remaining value already makes the path impossible
The real gain here is not just “using recursion”.
It is noticing that canonical order simplifies the whole problem.