#42 · Backtracking

Combination Sum

Given distinct positive integers and a target, return every unique combination of the numbers that adds up to the target. The same number may be used any number of times, and order inside a combination does not matter.

MediumLeetCode

Active
Found
Window
Visited
Rejected

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Backtracking (decision tree + path stack)

Build the answer one number at a time. Keep the numbers chosen so far in a path; when the path hits the target save it; when it cannot work, undo the last choice and try the next. The recursion is a depth-first walk of a tree where each branch means "add this candidate next".

Memory layout

One shared path array, mutated by push and pop, plus the recursion stack. Only copies of finished combinations are allocated.

Operation	Cost
time	O(N^(T/M)) worst case: N candidates, target T, smallest candidate M
space	O(T/M) path and recursion depth

Start index (canonical order)

Recurse with the index of the last chosen candidate so later picks never go back to a smaller index. Each multiset is generated exactly once, in one fixed order.

Memory layout

One integer per call.

Operation	Cost
duplicates produced	none

Why it fits

The answer is a set of choices, and each choice reduces the problem to the same question with a smaller target: that is recursion with undo.
Allowing a number to be reused means the recursive call passes the same index again; moving the index forward only is what forbids re-ordering.
Sorting turns "this number is too big" into "all remaining numbers are too big", so a whole range of branches can be cut with one comparison.

Why alternatives degrade

Generate all sequences then deduplicate:: The number of ordered sequences is much larger than the number of combinations: each combination of k numbers appears up to k! times.
Greedy:: Taking the largest number that fits misses valid answers; for [2,3,5] and 8 the greedy choice 5 gives only [3,5] and never finds [2,2,2,2].
Counting DP only:: A counting table says how many ways exist, not which ones. Listing them needs the combinations themselves (the table of lists).

Four approaches, from naive to production

1 · beginner

Every ordered sequence, sort and dedupe

time O(N^(T/M) · k log k)space O(number of results · k)

Recursively append any candidate to the path until the sum reaches or passes the target. When the sum equals the target, sort a copy of the path and add it to the result only if that sorted form has not been seen.

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    set<string> seen;
    vector<vector<int>> result;
    vector<int> path;
    function<void(int)> dfs = [&](int sum) {
        if (sum > target) return;
        if (sum == target) {
            vector<int> combo = path; sort(combo.begin(), combo.end());
            string key; for (int x : combo) key += to_string(x) + ",";
            if (!seen.count(key)) {
                seen.insert(key);
                result.push_back(combo);
            }
            return;
        }
        for (int c : candidates) {
            path.push_back(c);
            dfs(sum + c);
            path.pop_back();
        }
    };
    dfs(0);
    return result;
}

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    Set<String> seen = new HashSet<>();
    List<List<Integer>> result = new ArrayList<>();
    dfs(candidates, target, new ArrayList<>(), 0, seen, result);
    return result;
}
private void dfs(int[] candidates, int target, List<Integer> path, int sum, Set<String> seen, List<List<Integer>> result) {
    if (sum > target) return;
    if (sum == target) {
        List<Integer> combo = new ArrayList<>(path);
        Collections.sort(combo);
        String key = combo.toString();
        if (!seen.contains(key)) {
            seen.add(key);
            result.add(combo);
        }
        return;
    }
    for (int c : candidates) {
        path.add(c);
        dfs(candidates, target, path, sum + c, seen, result);
        path.remove(path.size() - 1);
    }
}

def combination_sum(candidates, target):
    seen = set()
    result = []
    def dfs(path, total):
        if total > target: return
        if total == target:
            combo = sorted(path)
            key = tuple(combo)
            if key not in seen:
                seen.add(key)
                result.append(combo)
            return
        for c in candidates:
            path.append(c)
            dfs(path, total + c)
            path.pop()
    dfs([], 0)
    return result

function combinationSum(candidates: number[], target: number): number[][] {
  const seen = new Set<string>();
  const result: number[][] = [];
  const dfs = (path: number[], sum: number): void => {
    if (sum > target) return;
    if (sum === target) {
      const combo = [...path].sort((a, b) => a - b);
      const key = combo.join(',');
      if (!seen.has(key)) {
        seen.add(key);
        result.push(combo);
      }
      return;
    }
    for (const c of candidates) {
      path.push(c);
      dfs(path, sum + c);
      path.pop();
    }
  };
  dfs([], 0);
  return result;
}

Flaws & bottlenecks

Each combination is generated in every ordering, so a combination of k numbers is found up to k! times.
Sorting and building a text key for every hit adds extra work.
No pruning other than stopping when the sum is too large.

Interviewer cross-questions

Why does the search produce duplicates?

Say: Each recursive level may pick any candidate, so [2,3,3], [3,2,3] and [3,3,2] are different paths to the same multiset. Nothing in the recursion forbids going back to a smaller number.

How do you avoid duplicates without a set?

Say: Pass a start index and only choose candidates at or after it. Then each multiset is built in exactly one order.

Why is the sum check ">" rather than "≥"?

Say: Equal sums are solutions and must be recorded. Only strictly larger sums are dead ends, because all candidates are positive.

2 · intermediate

Start index: no duplicates by construction

time O(N^(T/M))space O(T/M)

The recursion carries a start index. A call may pick any candidate from that index onwards and recurse with the same index (so numbers can repeat). Combinations are built in a single order, so no sorting or de-duplication is needed.

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<int>> result;
    vector<int> path;
    function<void(int, int)> dfs = [&](int start, int sum) {
        if (sum > target) return;
        if (sum == target) {
            result.push_back(path);
            return;
        }
        for (int i = start; i < (int)candidates.size(); i++) {
            path.push_back(candidates[i]);
            dfs(i, sum + candidates[i]);
            path.pop_back();
        }
    };
    dfs(0, 0);
    return result;
}

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<>();
    dfs(candidates, target, 0, 0, new ArrayList<>(), result);
    return result;
}
private void dfs(int[] candidates, int target, int start, int sum, List<Integer> path, List<List<Integer>> result) {
    if (sum > target) return;
    if (sum == target) {
        result.add(new ArrayList<>(path));
        return;
    }
    for (int i = start; i < candidates.length; i++) {
        path.add(candidates[i]);
        dfs(candidates, target, i, sum + candidates[i], path, result);
        path.remove(path.size() - 1);
    }
}

def combination_sum(candidates, target):
    result = []
    path = []
    def dfs(start, total):
        if total > target: return
        if total == target:
            result.append(path[:])
            return
        for i in range(start, len(candidates)):
            path.append(candidates[i])
            dfs(i, total + candidates[i])
            path.pop()
    dfs(0, 0)
    return result

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

Flaws & bottlenecks

When the sum passes the target the call returns, but the parent loop still tries every larger candidate and fails on each.
Each failed call still costs a function call and a path push/pop.
The candidate order matters for performance: large numbers first would fail faster than small ones.

Interviewer cross-questions

Why recurse with i and not i + 1?

Say: The same number may be reused, so the next pick may be the same index again. Using i + 1 would solve the "each number once" variant (Combination Sum II style).

How does the start index prevent duplicates?

Say: After choosing candidate i you can never choose an earlier one, so a combination is only ever listed in non-decreasing index order.

What can still be pruned?

Say: Sorting the candidates lets you stop the loop at the first candidate larger than the remaining sum, since all later ones are larger.

3 · advanced

Sorted candidates + break on overshoot

time O(N^(T/M)) worst case, much less in practicespace O(T/M)

Sort once, track the remaining sum instead of the running sum, and break out of the loop at the first candidate larger than the remainder. No branch that overshoots is ever created.

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<int> sorted = candidates; sort(sorted.begin(), sorted.end());
    vector<vector<int>> result;
    vector<int> path;
    function<void(int, int)> dfs = [&](int start, int remain) {
        if (remain == 0) {
            result.push_back(path);
            return;
        }
        for (int i = start; i < (int)sorted.size(); i++) {
            if (sorted[i] > remain) break;
            path.push_back(sorted[i]);
            dfs(i, remain - sorted[i]);
            path.pop_back();
        }
    };
    dfs(0, target);
    return result;
}

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    int[] sorted = candidates.clone(); Arrays.sort(sorted);
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    dfs(sorted, 0, target, path, result);
    return result;
}
private void dfs(int[] sorted, int start, int remain, List<Integer> path, List<List<Integer>> result) {
    if (remain == 0) {
        result.add(new ArrayList<>(path));
        return;
    }
    for (int i = start; i < sorted.length; i++) {
        if (sorted[i] > remain) break;
        path.add(sorted[i]);
        dfs(sorted, i, remain - sorted[i], path, result);
        path.remove(path.size() - 1);
    }
}

def combination_sum(candidates, target):
    sorted_c = sorted(candidates)
    result = []
    path = []
    def dfs(start, remain):
        if remain == 0:
            result.append(path[:])
            return
        for i in range(start, len(sorted_c)):
            if sorted_c[i] > remain: break
            path.append(sorted_c[i])
            dfs(i, remain - sorted_c[i])
            path.pop()
    dfs(0, target)
    return result

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

Flaws & bottlenecks

The sort costs O(N log N) up front (usually negligible).
Relies on candidates being positive: zero or negative numbers would make the recursion infinite.
The worst case is unchanged: many small candidates still produce a huge number of valid combinations.

Interviewer cross-questions

Why is break correct and not just continue?

Say: Candidates are sorted ascending, so if candidate i is too large, every later candidate is at least as large. Skipping them one by one would only repeat the same failed comparison.

What if the candidates contain zero or a negative number?

Say: The remaining sum could stay the same or grow, so the recursion would never terminate. The problem guarantees positive values; a production version should validate that.

What is the real bound on the output?

Say: The number of combinations itself can be exponential, so any algorithm that lists them is exponential in the worst case. This approach does only work proportional to the output plus the failed leaves.

4 · expert

Bottom-up table of combinations per sum

time O(N · T · total combinations built)space O(T · combinations)

Like the unbounded coin-change table, but each cell stores the actual combinations. Process candidates one at a time and, for every sum t, extend all combinations of t − c with c. No recursion, and the processing order alone prevents duplicates.

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<vector<int>>> table(target + 1);
    table[0].push_back({});
    for (int c : candidates) {
        for (int t = c; t <= target; t++) {
            for (const auto& combo : table[t - c]) {
                vector<int> next = combo; next.push_back(c); table[t].push_back(next);
            }
        }
    }
    return table[target];
}

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<List<Integer>>> table = new ArrayList<>();
    for (int t = 0; t <= target; t++) table.add(new ArrayList<>());
    table.get(0).add(new ArrayList<>());
    for (int c : candidates) {
        for (int t = c; t <= target; t++) {
            for (List<Integer> combo : table.get(t - c)) {
                List<Integer> next = new ArrayList<>(combo);
                next.add(c);
                table.get(t).add(next);
            }
        }
    }
    return table.get(target);
}

def combination_sum(candidates, target):
    table = [[] for _ in range(target + 1)]
    table[0].append([])
    for c in candidates:
        for t in range(c, target + 1):
            for combo in table[t - c]: table[t].append(combo + [c])
    return table[target]

function combinationSum(candidates: number[], target: number): number[][] {
  const table: number[][][] = Array.from({ length: target + 1 }, () => []);
  table[0].push([]);
  for (const c of candidates) {
    for (let t = c; t <= target; t++) {
      for (const combo of table[t - c]) table[t].push([...combo, c]);
    }
  }
  return table[target];
}

Flaws & bottlenecks

It stores the combinations of every intermediate sum, even ones that never lead to the target, so memory can be much larger than the answer.
Copying a combination for every extension adds extra work compared with a shared path.
There is no early termination or pruning by magnitude.

Interviewer cross-questions

Why is there no duplicate if the loops are candidate-outer?

Say: A combination is only ever extended with the current candidate, and earlier candidates are already finished. So numbers appear in the order they were processed, one fixed order for each multiset.

When is this better than backtracking?

Say: When recursion depth is a concern (very small candidates with a huge target) or when you also need the answers for several targets at once: the table already contains them.

What if you only need the number of combinations?

Say: Keep a count instead of a list: ways[t] += ways[t − c]. That is O(N · T) time and O(T) space, the classic coin-change counting DP.

Synchronized code walkthrough

Showing: Every ordered sequence, sort and dedupe — shares the player above; click any step to jump.

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    set<string> seen;
    vector<vector<int>> result;
    vector<int> path;
    function<void(int)> dfs = [&](int sum) {
        if (sum > target) return;
        if (sum == target) {
            vector<int> combo = path; sort(combo.begin(), combo.end());
            string key; for (int x : combo) key += to_string(x) + ",";
            if (!seen.count(key)) {
                seen.insert(key);
                result.push_back(combo);
            }
            return;
        }
        for (int c : candidates) {
            path.push_back(c);
            dfs(sum + c);
            path.pop_back();
        }
    };
    dfs(0);
    return result;
}

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    Set<String> seen = new HashSet<>();
    List<List<Integer>> result = new ArrayList<>();
    dfs(candidates, target, new ArrayList<>(), 0, seen, result);
    return result;
}
private void dfs(int[] candidates, int target, List<Integer> path, int sum, Set<String> seen, List<List<Integer>> result) {
    if (sum > target) return;
    if (sum == target) {
        List<Integer> combo = new ArrayList<>(path);
        Collections.sort(combo);
        String key = combo.toString();
        if (!seen.contains(key)) {
            seen.add(key);
            result.add(combo);
        }
        return;
    }
    for (int c : candidates) {
        path.add(c);
        dfs(candidates, target, path, sum + c, seen, result);
        path.remove(path.size() - 1);
    }
}

def combination_sum(candidates, target):
    seen = set()
    result = []
    def dfs(path, total):
        if total > target: return
        if total == target:
            combo = sorted(path)
            key = tuple(combo)
            if key not in seen:
                seen.add(key)
                result.append(combo)
            return
        for c in candidates:
            path.append(c)
            dfs(path, total + c)
            path.pop()
    dfs([], 0)
    return result

function combinationSum(candidates: number[], target: number): number[][] {
  const seen = new Set<string>();
  const result: number[][] = [];
  const dfs = (path: number[], sum: number): void => {
    if (sum > target) return;
    if (sum === target) {
      const combo = [...path].sort((a, b) => a - b);
      const key = combo.join(',');
      if (!seen.has(key)) {
        seen.add(key);
        result.push(combo);
      }
      return;
    }
    for (const c of candidates) {
      path.push(c);
      dfs(path, sum + c);
      path.pop();
    }
  };
  dfs([], 0);
  return result;
}

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<int>> result;
    vector<int> path;
    function<void(int, int)> dfs = [&](int start, int sum) {
        if (sum > target) return;
        if (sum == target) {
            result.push_back(path);
            return;
        }
        for (int i = start; i < (int)candidates.size(); i++) {
            path.push_back(candidates[i]);
            dfs(i, sum + candidates[i]);
            path.pop_back();
        }
    };
    dfs(0, 0);
    return result;
}

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<>();
    dfs(candidates, target, 0, 0, new ArrayList<>(), result);
    return result;
}
private void dfs(int[] candidates, int target, int start, int sum, List<Integer> path, List<List<Integer>> result) {
    if (sum > target) return;
    if (sum == target) {
        result.add(new ArrayList<>(path));
        return;
    }
    for (int i = start; i < candidates.length; i++) {
        path.add(candidates[i]);
        dfs(candidates, target, i, sum + candidates[i], path, result);
        path.remove(path.size() - 1);
    }
}

def combination_sum(candidates, target):
    result = []
    path = []
    def dfs(start, total):
        if total > target: return
        if total == target:
            result.append(path[:])
            return
        for i in range(start, len(candidates)):
            path.append(candidates[i])
            dfs(i, total + candidates[i])
            path.pop()
    dfs(0, 0)
    return result

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

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<int> sorted = candidates; sort(sorted.begin(), sorted.end());
    vector<vector<int>> result;
    vector<int> path;
    function<void(int, int)> dfs = [&](int start, int remain) {
        if (remain == 0) {
            result.push_back(path);
            return;
        }
        for (int i = start; i < (int)sorted.size(); i++) {
            if (sorted[i] > remain) break;
            path.push_back(sorted[i]);
            dfs(i, remain - sorted[i]);
            path.pop_back();
        }
    };
    dfs(0, target);
    return result;
}

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    int[] sorted = candidates.clone(); Arrays.sort(sorted);
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    dfs(sorted, 0, target, path, result);
    return result;
}
private void dfs(int[] sorted, int start, int remain, List<Integer> path, List<List<Integer>> result) {
    if (remain == 0) {
        result.add(new ArrayList<>(path));
        return;
    }
    for (int i = start; i < sorted.length; i++) {
        if (sorted[i] > remain) break;
        path.add(sorted[i]);
        dfs(sorted, i, remain - sorted[i], path, result);
        path.remove(path.size() - 1);
    }
}

def combination_sum(candidates, target):
    sorted_c = sorted(candidates)
    result = []
    path = []
    def dfs(start, remain):
        if remain == 0:
            result.append(path[:])
            return
        for i in range(start, len(sorted_c)):
            if sorted_c[i] > remain: break
            path.append(sorted_c[i])
            dfs(i, remain - sorted_c[i])
            path.pop()
    dfs(0, target)
    return result

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

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<vector<int>>> table(target + 1);
    table[0].push_back({});
    for (int c : candidates) {
        for (int t = c; t <= target; t++) {
            for (const auto& combo : table[t - c]) {
                vector<int> next = combo; next.push_back(c); table[t].push_back(next);
            }
        }
    }
    return table[target];
}

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<List<Integer>>> table = new ArrayList<>();
    for (int t = 0; t <= target; t++) table.add(new ArrayList<>());
    table.get(0).add(new ArrayList<>());
    for (int c : candidates) {
        for (int t = c; t <= target; t++) {
            for (List<Integer> combo : table.get(t - c)) {
                List<Integer> next = new ArrayList<>(combo);
                next.add(c);
                table.get(t).add(next);
            }
        }
    }
    return table.get(target);
}

def combination_sum(candidates, target):
    table = [[] for _ in range(target + 1)]
    table[0].append([])
    for c in candidates:
        for t in range(c, target + 1):
            for combo in table[t - c]: table[t].append(combo + [c])
    return table[target]

function combinationSum(candidates: number[], target: number): number[][] {
  const table: number[][][] = Array.from({ length: target + 1 }, () => []);
  table[0].push([]);
  for (const c of candidates) {
    for (let t = c; t <= target; t++) {
      for (const combo of table[t - c]) table[t].push([...combo, c]);
    }
  }
  return table[target];
}