← DSA Atlas
Dedicated problem page · #39

Combination Sum

MediumBacktrackingCombination search with unlimited reuseBacktracking with a non-advancing start index
Solve on LeetCode ↗
39
MediumBacktrackingBacktracking with a non-advancing start indexCombination search with unlimited reuse

Combination Sum

Given an array of distinct integers candidates and a target integer, return all unique combinations of candidates where the chosen numbers sum to target. The same number may be chosen an unlimited number of times. Two combinations are unique if the multiset of chosen numbers differs.

Open official problem prompt ↗
In plain English

Enumerate every multiset of candidates (repeats allowed) whose sum equals the target, with no combination listed twice.

Picture it like this

Making exact change for a price using coins of unlimited supply: you can use several of the same coin, but [nickel, dime] and [dime, nickel] are the same handful of coins.

Example
Input
candidates = [2, 3, 6, 7], target = 7
Output
[[2,2,3], [7]]
Why
2+2+3 = 7 and 7 = 7 are the only ways to reach 7; e.g. 2+2+2 = 6 falls short and adding another 2 overshoots.
Constraints
1 <= candidates.length <= 302 <= candidates[i] <= 40All elements of candidates are distinct1 <= target <= 40
Pattern lesson

See the pattern, then code

Combination search with unlimited reuse
Recognition clue

Asking for all combinations summing to a target WITH repetition allowed is the signature; the small target bound makes exhaustive search viable.

↗
Backtracking

Generate every valid combination, permutation, partition, or configuration.. Reuse is modeled by recursing with the same index i (not i + 1), letting a candidate repeat; passing i as the new start still forbids going back to earlier candidates, which prevents permutation-style duplicates like [2,3] and [3,2].

New words, made simpleKnow these before the algorithm
Combination
An unordered selection; only which numbers and how many, not their order, matters.
Remaining
Target minus the sum of the current path; the amount still to be filled.
Non-advancing start
Recursing with the same index i so a candidate may be reused, while still barring earlier candidates.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Generate all sequences then dedupe

Wastes effort generating and discarding duplicates; the ordering discipline of the start index avoids this entirely.

Build sequences allowing any order and reuse, then collapse permutations to a canonical form in a set.

Time Exponential, far worseSpace Large
Best choiceBacktracking with same-index reuse

Directly enforces uniqueness and reuse in one clean recursion; the standard accepted solution.

DFS carrying remaining; pick a candidate, recurse with the same index to allow repeats, prune when a candidate exceeds remaining.

Time O(N^(T/M + 1))Space O(T/M)
The rule we keep true

Invariant

path contains candidates chosen at indices >= the current start (in non-decreasing index order), and their sum plus remaining always equals target.

Why this is correct

Reasoning

Because we never move start backward, combinations are always built in non-decreasing index order, so each multiset has exactly one canonical path. Recursing with the same i permits repetition; the remaining == 0 base case captures exactly the sums that hit the target, and pruning candidates > remaining removes impossible branches without losing any solution.

The algorithm in three movesSay these aloud before coding
1Track the remaining amount still needed

path=[2] rem=5

2When remaining hits 0, record a copy of the path

path=[2,2] rem=3

3Loop from the current start; skip a candidate larger than remaining, else pick it and recurse with the SAME index i so it can repeat

path=[2,2,3] rem=0 -> record

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
20
31
62
73
1 · Readstart=0, rem=7
2 · AskPick candidates[0]=2?
3 · Update statepath=[]
4 · ResultPick 2, rem=5, recurse start=0
Key takeaway

From remaining 7, the branch 2 -> 2 -> 3 reaches 0 and is recorded as a valid combination.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 8-10Success base case

    When remaining is exactly 0 the current path is a valid combination; record a copy and stop.

  2. 2
    Lines 11-13Prune impossible picks

    Skip any candidate larger than remaining; it can never contribute to hitting the target on this branch.

  3. 3
    Lines 14-16Reuse via same index

    Recursing with backtrack(i, ...) rather than i + 1 lets the same candidate be chosen again, enabling repetition.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • No combination sums to target -> returns []
  • A single candidate equal to target -> [[target]]
  • Smallest candidate divides target -> a long all-same-number combination like many 2s
!

Common beginner mistakes

  • Recursing with i + 1, which forbids reuse and yields wrong answers
  • Using remaining < 0 as the only base case without pruning, which still works but explores dead branches
  • Recording path by reference instead of a copy
Check your understanding

Why can we recurse with the same index i without producing duplicate combinations like [2,3] and [3,2]?

More in Backtracking

#78SubsetsSubset enumeration by include/exclude#46PermutationsPermutation generation#79Word SearchGrid path search with in-place visited marking#17Letter Combinations of a Phone NumberCartesian product of digit-letter groups#22Generate ParenthesesConstrained string construction#37Sudoku SolverConstrained cell filling with backtracking