Combination Sum — Backtracking

What does it solve?

Given a set of distinct candidates and a target, find every unique combination of candidates that sums exactly to the target. Each candidate may be used an unlimited number of times.

We explore candidates from a starting index forward (never looking back), either picking the current candidate again (staying at the same index) or moving on to the next index. We prune as soon as the running sum exceeds the target.

The core idea

// backtrack(start, remaining):
if remaining == 0: record(path)
for i = start to n-1:
  if cand[i] > remaining: break
  path.push(cand[i])
  backtrack(i, remaining - cand[i])
  path.pop() // backtrack

Complexity

Time complexity

O(2^T)

Worst case is exponential in the target value T, heavily pruned by sorting candidates and cutting off once the running sum exceeds the target.

Space complexity

O(T / min)

Recursion depth is bounded by the target divided by the smallest candidate — the maximum possible path length.

Examples & edge cases

Live animation

Trying this candidate Too large (pruned) In current path Combination recorded

Target —

−

Sum so far —

Remaining —

Current path → [ ]

Step — of —

Start index

—

Action

—

Path depth

—

elements

Found

—

combinations

Select an example and press Play to start.

Combinations found so far

none yet

✓ Complete

Speed Medium

Step-by-step table

Step	Index	Candidate	Action	Path	Remaining

C++ implementation

combination_sum.cpp

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> result;

void backtrack(vector<int>& cand, int start,
               int remaining, vector<int>& path) {
    if (remaining == 0) {
        result.push_back(path);          // found a valid combination
        return;
    }

    for (int i = start; i < cand.size(); i++) {
        if (cand[i] > remaining) break;  // prune (cand sorted ascending)

        path.push_back(cand[i]);
        backtrack(cand, i, remaining - cand[i], path); // reuse cand[i]: pass i, not i+1
        path.pop_back();                 // backtrack
    }
}

int main() {
    vector<int> candidates = {2, 3, 6, 7};
    int target = 7;

    sort(candidates.begin(), candidates.end());  // enables pruning
    vector<int> path;
    backtrack(candidates, 0, target, path);

    cout << "Total combinations: " << result.size() << "\n";
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars