Combination Sum

Backtracking with reuse and a start pointer

Unbounded choices. How do you avoid duplicates?

Published Apr 16, 2026

Problem

Given an array of distinct positive integers candidates and a target target, return all unique combinations (as lists) whose numbers sum to target. Each number may be used an unlimited number of times. Combinations are unordered — [2, 2, 3] and [3, 2, 2] are the same.

Input

candidates = [2, 3, 6, 7], target = 7

Output

[[2, 2, 3], [7]]

Input

candidates = [2, 3, 5], target = 8

Output

[[2, 2, 2, 2], [2, 3, 3], [3, 5]]

Intuition

Two small twists over subsets:

Reuse. At each recursive call, you can pick the same index again. So the recurse-with call is dfs(i, ...) rather than dfs(i + 1, ...).
Dedup by ordering. To avoid emitting [2, 2, 3] and [3, 2, 2] as distinct, force the path to be non-decreasing by only considering indices ≥ start.

The start pointer does both jobs. It's the same knob as in subsets (#78), just tuned differently — subsets use start + 1 (each element once, order fixed by array); combination sum uses start (reuse allowed, order fixed by start).

Pruning helps a lot: sort candidates ascending, break out of the loop as soon as candidates[i] > remaining. Without sort, the candidate space can explode; with sort, the tree is much shallower.

Approach

Sorted backtracking with pruning

TimeO(n^(T/min))

SpaceO(T/min)

Recommended

Sort once, then classic backtracking with two tweaks: dfs(i, ...) allows reuse, and break when the remaining target drops below the current candidate.

The depth of the recursion is bounded by target / min(candidate); the branching factor shrinks with pruning.

impl Solution {
    pub fn combination_sum(mut candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
        candidates.sort();
        let mut out = Vec::new();
        let mut path = Vec::new();
        fn dfs(
            start: usize,
            remaining: i32,
            cand: &[i32],
            path: &mut Vec<i32>,
            out: &mut Vec<Vec<i32>>,
        ) {
            if remaining == 0 {
                out.push(path.clone());
                return;
            }
            for i in start..cand.len() {
                if cand[i] > remaining {
                    break;
                }
                path.push(cand[i]);
                dfs(i, remaining - cand[i], cand, path, out);
                path.pop();
            }
        }
        dfs(0, target, &candidates, &mut path, &mut out);
        out
    }
}

Rust · runnable

function combinationSum(candidates: number[], target: number): number[][] {
  const sorted = [...candidates].sort((a, b) => a - b);
  const out: number[][] = [];
  const path: number[] = [];
  const dfs = (start: number, remaining: number): void => {
    if (remaining === 0) {
      out.push(path.slice());
      return;
    }
    for (let i = start; i < sorted.length; i++) {
      if (sorted[i] > remaining) break;
      path.push(sorted[i]);
      dfs(i, remaining - sorted[i]);
      path.pop();
    }
  };
  dfs(0, target);
  return out;
}

TypeScript · runnable

Unsorted backtracking (no pruning)

TimeO(n^(T/min))

SpaceO(T/min)

Without sorting, you keep the start pointer for dedup but can't early-break on a too-large candidate. Slower in practice on most inputs, but useful as a baseline to see why the sort matters.

impl Solution {
    pub fn combination_sum(candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
        let mut out = Vec::new();
        let mut path = Vec::new();
        fn dfs(
            start: usize,
            remaining: i32,
            cand: &[i32],
            path: &mut Vec<i32>,
            out: &mut Vec<Vec<i32>>,
        ) {
            if remaining == 0 {
                out.push(path.clone());
                return;
            }
            if remaining < 0 {
                return;
            }
            for i in start..cand.len() {
                path.push(cand[i]);
                dfs(i, remaining - cand[i], cand, path, out);
                path.pop();
            }
        }
        dfs(0, target, &candidates, &mut path, &mut out);
        out
    }
}

Rust · runnable

function combinationSum(candidates: number[], target: number): number[][] {
  const out: number[][] = [];
  const path: number[] = [];
  const dfs = (start: number, remaining: number): void => {
    if (remaining === 0) {
      out.push(path.slice());
      return;
    }
    if (remaining < 0) return;
    for (let i = start; i < candidates.length; i++) {
      path.push(candidates[i]);
      dfs(i, remaining - candidates[i]);
      path.pop();
    }
  };
  dfs(0, target);
  return out;
}

TypeScript · runnable

Trace

Sorted candidates = [2, 3, 6, 7], target = 7:

step	start	path	remaining	action
1	0	[]	7	try 2
2	0	[2]	5	try 2 again
3	0	[2,2]	3	try 2, then try 3
4	0	[2,2,2]	1	2 > 1 break
5	1	[2,2,3]	0	emit
6	1	[2,3]	2	3 > 2 break
7	2	[2,6]	-1	pruned (doesn't happen with pre-check)
8	3	[7]	0	emit

Two combinations: [2, 2, 3] and [7].

Edge cases

No combination sums to target — return [].
Target of 0 — the only combination is []; the base case handles it.
Single candidate that divides target — one combination of target / candidate copies.
Very small minimum candidate with large target — depth can be target / min; for the problem's stated constraints this is small (target ≤ 40, candidates ≥ 2).

Takeaway

The start pointer is the dedup mechanism for unordered combinations. Subsets use start + 1; combination-sum uses start. When you need to emit multisets without worrying about order, impose an order on the path itself (non-decreasing indices). This is the same idea as "canonical form" in set enumeration.

Medium#78

Subsets

The canonical backtracking template. Include or exclude each element.

Medium#46

Permutations

Backtracking with a ‘used’ set. Draw the decision tree.

Medium#131

Palindrome Partitioning

Backtrack on where to cut. Precompute palindrome checks with DP.