Coding interview problems › Backtracking

🧩 Backtracking Medium

Combination Sum

Combination Sum explained: backtracking with reuse and pruning to list every combination that adds to a target, tested Python, pitfalls and a live visual.

Also searched as: combination sum backtracking · find all combinations that sum to target · combination sum with repetition

🧩

Try it live Free

Backtracking: Subsets, Permutations & Pruning

Switch on pruning in the Backtracking lab and watch the explored-node counter collapse while the answers stay exactly the same, the same effect the early break has here.

Also useful: Coin Change (DP)

Open the playground →

The problem

Given a list of distinct positive integers and a target, return every unique combination of the numbers that adds up to target. A number may be used any number of times. Combinations that differ only in order count as the same.

Inputcandidates = [2, 3, 6, 7], target = 7
Output[[2, 2, 3], [7]]
Inputcandidates = [2, 3, 5], target = 8
Output[[2, 2, 2, 2], [2, 3, 3], [3, 5]]

The key insight

Build combinations in non-decreasing index order so each combination is generated once. After choosing candidates[i], recurse with the same i (the number can be reused) and a smaller remaining target. With the candidates sorted, once a number is bigger than what remains, every later number is too, so you can prune the whole loop.

Brute force first: Generating every multiset of candidates up to the target and filtering is far more work than needed, since most branches overshoot early.

Step-by-step approach

  1. Sort the candidates.
  2. Define dfs(start, remain). If remain == 0, record a copy of path.
  3. Loop i from start. If candidates[i] > remain, break (pruning).
  4. Choose candidates[i], call dfs(i, remain - candidates[i]) (same i allows reuse), then pop.
  5. Call dfs(0, target).

Python solution

PYTHON 3tested
def combination_sum(candidates, target):
    candidates = sorted(candidates)
    out, path = [], []

    def dfs(start, remain):
        if remain == 0:
            out.append(path[:])
            return
        for i in range(start, len(candidates)):
            c = candidates[i]
            if c > remain:
                break                  # sorted, so the rest are too big
            path.append(c)
            dfs(i, remain - c)         # i, not i + 1: reuse allowed
            path.pop()

    dfs(0, target)
    return out

Complexity

TimeExponential, about O(n^(T/m))
SpaceO(T/m)

With target T and smallest candidate m, the recursion is at most T/m deep and branches up to n ways, so the worst case is exponential. Pruning cuts most branches in practice.

Common mistakes

Frequently asked questions

What is the time and space complexity of Combination Sum?

Exponential in the worst case, roughly O(n^(T/m)) where T is the target and m the smallest candidate. The recursion depth and path are O(T/m).

How is Combination Sum II different?

Each number may be used once and the input can contain duplicates. Recurse with i + 1, sort the input, and skip candidates[i] when i > start and it equals candidates[i - 1].

How is this related to Coin Change II?

Coin Change II counts the same combinations without listing them, so a DP over amounts is enough. Combination Sum must list every combination, so backtracking is natural.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Backtracking Backtracking: Subsets, Permutations & Pruning lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.