Backtracking: Subsets and Combinations

EditorialUpdated Oct 31, 2026

One decision per value

List every subset of [1, 2, 3]. With three values you could write three nested loops, but the next input has ten values, or twenty, and you can't write a loop per value. Look at it another way: a subset is just a decision for each value, take it or skip it. Three values, two choices each, 2³ = 8 subsets.

Those decisions form a tree. The root has decided nothing, each level decides one value, and each leaf is one complete subset. Searching it depth-first, with one list for the choices you're holding and an undo on the way back, is backtracking:

A tree of shaded discs on three levels, labelled down the left decide 1, decide 2 and decide 3: the root disc is 1, its two children are 2s, and their four children are 3s, each level its own colour. From every disc a solid green edge goes left, take, and a dashed grey edge goes right, skip, with pills beside the first two reading take 1 and skip 1. The eight leaves are tiles holding the subsets 1 2 3, 1 2, 1 3, 1, 2 3, 2, 3 and none. One path is drawn thick in purple, take 1, skip 2, take 3, its discs ringed, ending at the ringed tile 1 3, with a pill under the leaves reading path: take 1, skip 2, take 3. Focal line: each level decides one value, so n values give 2ⁿ leaves. Title: take or skip each value.

Choose, explore, unchoose

One list, path, holds the choices made so far. At index i, choose to take nums[i] (append it), explore the rest with a call on i + 1, then unchoose (pop it) and explore again without it. When i reaches the end, every value is decided and the path is one subset:

void takeOrSkip(const vector<int>& nums, int i, vector<int>& path, vector<vector<int>>& out) {
    if (i == (int)nums.size()) {           // every value decided: one subset
        out.push_back(path);               // a copy: path keeps changing after this
        return;
    }
    path.push_back(nums[i]);               // choose: take nums[i]
    takeOrSkip(nums, i + 1, path, out);    // explore
    path.pop_back();                       // unchoose
    takeOrSkip(nums, i + 1, path, out);    // and the other branch: skip it
}

vector<vector<int>> subsets(const vector<int>& nums) {
    vector<vector<int>> out;
    vector<int> path;
    takeOrSkip(nums, 0, path, out);
    return out;
}

def subsets(nums):
    out, path = [], []

    def take_or_skip(i):
        if i == len(nums):              # every value decided: one subset
            out.append(path[:])         # a copy: path keeps changing after this
            return
        path.append(nums[i])            # choose: take nums[i]
        take_or_skip(i + 1)             # explore
        path.pop()                      # unchoose
        take_or_skip(i + 1)             # and the other branch: skip it

    take_or_skip(0)
    return out

static void takeOrSkip(int[] nums, int i, List<Integer> path, List<List<Integer>> out) {
    if (i == nums.length) {                 // every value decided: one subset
        out.add(new ArrayList<>(path));     // a copy: path keeps changing after this
        return;
    }
    path.add(nums[i]);                      // choose: take nums[i]
    takeOrSkip(nums, i + 1, path, out);     // explore
    path.remove(path.size() - 1);           // unchoose
    takeOrSkip(nums, i + 1, path, out);     // and the other branch: skip it
}

static List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> out = new ArrayList<>();
    takeOrSkip(nums, 0, new ArrayList<>(), out);
    return out;
}

function subsets(nums) {
    const out = [], path = [];
    function takeOrSkip(i) {
        if (i === nums.length) {            // every value decided: one subset
            out.push([...path]);            // a copy: path keeps changing after this
            return;
        }
        path.push(nums[i]);                 // choose: take nums[i]
        takeOrSkip(i + 1);                  // explore
        path.pop();                         // unchoose
        takeOrSkip(i + 1);                  // and the other branch: skip it
    }
    takeOrSkip(0);
    return out;
}

Each printed [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []], taking before skipping. Step through it on [1, 2, 3]:

Take or skip, on [1, 2, 3] — Green values were taken, grey ones skipped, indigo is the one being decided. The row below is the shared path.

Two details carry the whole technique. The pop after the first call is what lets one list serve every branch: the second call sees exactly the choices above it, as if the first never happened. And the leaf stores a copy of the path, path[:]: the path keeps changing after this, and a stored reference would change with it.

A loop at each node, and duplicates

There's a second shape for the same search. Each call records the path as a subset, then loops over the values after the last one taken and tries each as the next. A start index keeps the values in index order, so [2, 1] is never built after [1, 2]. Every node is now an answer, so the tree is smaller: for 3 values, 8 calls against 15 for take or skip; for 16 values, 65,536 against 131,071.

This shape handles duplicates. Subsets II gives [1, 2, 2], and the two 2s would build [2] twice. Sort the values so equal ones sit together, then, within one call's loop, skip a value equal to the one it just tried:

The loop tree for the sorted [1, 2, 2], each node a tile holding its subset. From the root, none, edges lead to 1, to 2, and to a second 2 that is pale and joined by a dashed red edge with a pill reading repeat. Under 1, edges lead to 1 2 and to a second 1 2 that is pale and marked repeat the same way. Under 1 2, a green edge leads to 1 2 2, and under 2 another, tagged new loop, leads to 2 2. Beside the tree, a ticked card reads 6 subsets, none of them twice: [], [1], [1, 2], [1, 2, 2], [2], [2, 2]; below it a crossed card reads no skip: 8, [2] twice, [1, 2] twice. Focal line: each loop tries a value once; a deeper loop may take it again. Title: skip a repeat in the same loop.

void fromStart(const vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& out) {
    out.push_back(path);                               // every node of this tree is a subset
    for (int i = start; i < (int)nums.size(); i++) {
        if (i > start && nums[i] == nums[i - 1]) continue;   // this value was already tried at this depth
        path.push_back(nums[i]);
        fromStart(nums, i + 1, path, out);             // only later values from here: no reordering
        path.pop_back();
    }
}

vector<vector<int>> subsetsWithDup(vector<int> nums) {
    sort(nums.begin(), nums.end());                    // equal values side by side
    vector<vector<int>> out;
    vector<int> path;
    fromStart(nums, 0, path, out);
    return out;
}

def subsets_with_dup(nums):
    nums = sorted(nums)                     # equal values side by side
    out, path = [], []

    def from_start(start):
        out.append(path[:])                 # every node of this tree is a subset
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue                    # this value was already tried at this depth
            path.append(nums[i])
            from_start(i + 1)               # only later values from here: no reordering
            path.pop()

    from_start(0)
    return out

static void fromStart(int[] nums, int start, List<Integer> path, List<List<Integer>> out) {
    out.add(new ArrayList<>(path));                    // every node of this tree is a subset
    for (int i = start; i < nums.length; i++) {
        if (i > start && nums[i] == nums[i - 1]) continue;   // this value was already tried at this depth
        path.add(nums[i]);
        fromStart(nums, i + 1, path, out);             // only later values from here: no reordering
        path.remove(path.size() - 1);
    }
}

static List<List<Integer>> subsetsWithDup(int[] nums) {
    int[] sorted = nums.clone();
    Arrays.sort(sorted);                               // equal values side by side
    List<List<Integer>> out = new ArrayList<>();
    fromStart(sorted, 0, new ArrayList<>(), out);
    return out;
}

function subsetsWithDup(nums) {
    const sorted = [...nums].sort((a, b) => a - b);    // equal values side by side
    const out = [], path = [];
    function fromStart(start) {
        out.push([...path]);                           // every node of this tree is a subset
        for (let i = start; i < sorted.length; i++) {
            if (i > start && sorted[i] === sorted[i - 1]) continue;   // this value was already tried at this depth
            path.push(sorted[i]);
            fromStart(i + 1);                          // only later values from here: no reordering
            path.pop();
        }
    }
    fromStart(0);
    return out;
}

Each sorted [2, 1, 2] and printed [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]: six subsets, none twice. The test is i > start, not i > 0. Within one call's loop, the first copy of a value already builds every subset that puts it in this position, so a later copy can only repeat them. But a deeper call starts a loop of its own at start, and there the second copy comes first and is allowed: that's how [2, 2] gets built.

Cut what can't reach the target

Combination Sum asks for every combination of candidates that adds up to a target, and a candidate can be used as often as you like. Recurse with i, not i + 1, so the same number can come again. And sort the candidates: once one is bigger than what's left of the target, every later one is too, so the loop can stop at once:

void fill(const vector<int>& c, int start, int left, vector<int>& path, vector<vector<int>>& out) {
    if (left == 0) {                                   // the path adds up to the target
        out.push_back(path);
        return;
    }
    for (int i = start; i < (int)c.size(); i++) {
        if (c[i] > left) break;                        // sorted: every later candidate is too big as well
        path.push_back(c[i]);
        fill(c, i, left - c[i], path, out);            // i, not i + 1: the same number can be used again
        path.pop_back();
    }
}

vector<vector<int>> combinationSum(vector<int> candidates, int target) {
    sort(candidates.begin(), candidates.end());
    vector<vector<int>> out;
    vector<int> path;
    fill(candidates, 0, target, path, out);
    return out;
}

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

    def fill(start, left):
        if left == 0:                       # the path adds up to the target
            out.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > left:
                break                       # sorted: every later candidate is too big as well
            path.append(candidates[i])
            fill(i, left - candidates[i])   # i, not i + 1: the same number can be used again
            path.pop()

    fill(0, target)
    return out

static void fill(int[] c, int start, int left, List<Integer> path, List<List<Integer>> out) {
    if (left == 0) {                                   // the path adds up to the target
        out.add(new ArrayList<>(path));
        return;
    }
    for (int i = start; i < c.length; i++) {
        if (c[i] > left) break;                        // sorted: every later candidate is too big as well
        path.add(c[i]);
        fill(c, i, left - c[i], path, out);            // i, not i + 1: the same number can be used again
        path.remove(path.size() - 1);
    }
}

static List<List<Integer>> combinationSum(int[] candidates, int target) {
    int[] c = candidates.clone();
    Arrays.sort(c);
    List<List<Integer>> out = new ArrayList<>();
    fill(c, 0, target, new ArrayList<>(), out);
    return out;
}

function combinationSum(candidates, target) {
    const c = [...candidates].sort((a, b) => a - b);
    const out = [], path = [];
    function fill(start, left) {
        if (left === 0) {                              // the path adds up to the target
            out.push([...path]);
            return;
        }
        for (let i = start; i < c.length; i++) {
            if (c[i] > left) break;                    // sorted: every later candidate is too big as well
            path.push(c[i]);
            fill(i, left - c[i]);                      // i, not i + 1: the same number can be used again
            path.pop();
        }
    }
    fill(0, target);
    return out;
}

Each printed [[2, 2, 3], [7]] for target 7 and [[2, 2, 2, 2], [2, 3, 3], [3, 5]] for target 8. That break removes a whole fan of branches in one go:

Two dashed zones. One call, 5 left: the path holds a tile reading 2, beside text reading target 7, so 5 left. Under it, the sorted candidates as tiles: 2 and 3 in green, labelled fits, with 3 left and 2 left under them; 6 in red, labelled too big, with 6 > 5 under it; and 7 pale and dashed, labelled skipped, with 7 > 6. A dashed red line between 3 and 6 carries a pill reading break, and a line under the tiles reads 7 comes after 6, so it's bigger too: never tried. The whole search: for candidates 2 to 31 and target 40, a crossed card reads no cut, 635,408 calls, and a ticked card reads with the cut, 37,271 calls, over 6,131 answers either way. Focal line: sorted, the first candidate that's too big stops the loop. Title: a cut removes every later branch.

Counted on the candidates 2 to 31 and target 40: 6,131 combinations either way, but 635,408 calls without the cut and 37,271 with it, 172 ms against 20 ms in Python.

Two relatives change one rule each. Combination Sum II uses each candidate once, so it recurses with i + 1, and its input has repeats, so it sorts and skips equal neighbours as Subsets II did. Combination Sum III picks exactly k distinct digits from 1 to 9: stop when the path holds k values, and cut when the sum passes the target.

How big the tree gets

Backtracking visits every branch it doesn't cut, so the answer count sets a floor: 2ⁿ subsets, C(n, k) combinations, and copying each one out costs its length. The cuts decide how close you get to that floor. Combinations picks k numbers from 1 to n; a branch that can't fill k slots from the numbers left can stop:

def combine(n, k):
    out, path = [], []

    def pick(start):
        if len(path) == k:
            out.append(path[:])
            return
        for x in range(start, n + 1):
            if n - x + 1 < k - len(path):
                break                       # too few values left to fill the remaining slots
            path.append(x)
            pick(x + 1)
            path.pop()

    pick(1)
    return out

combine(4, 2) returned [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]. Generate Parentheses builds every balanced string of n pairs, and two counts decide each step: an opening bracket while fewer than n are open, a closing one while fewer have closed than opened:

def generate_parenthesis(n):
    out, path = [], []

    def build(opened, closed):
        if len(path) == 2 * n:
            out.append("".join(path))
            return
        if opened < n:                      # room for another (
            path.append("(")
            build(opened + 1, closed)
            path.pop()
        if closed < opened:                 # a ) has to close something already open
            path.append(")")
            build(opened, closed + 1)
            path.pop()

    build(0, 0)
    return out

For n = 3 it returned ['((()))', '(()())', '(())()', '()(())', '()()()'], and for n = 4, 14 strings. Counted:

Search	Answers	Calls without the cut	Calls with it
Combinations, n = 20, k = 10	184,756	616,666	352,716
Generate Parentheses, n = 8	1,430	131,071	6,917
Combination Sum, 2 to 31, target 40	6,131	635,408	37,271

Without its counts, Generate Parentheses would build all 2¹⁶ strings of 16 brackets and keep the balanced ones; with them, it never starts a string that can't be balanced.

Below, you run the search yourself. Candidates are sorted; at each step, take the next candidate, back up, record the path when it hits the target, or cut the rest when the next candidate no longer fits. A wrong move is refused with the reason.

Grow the Decision Tree: you take, back up, record and cut

Spotting it, and when it breaks

The clues. "All subsets", "all combinations", "every way to", "generate all", with an input small enough that the answers themselves fit: n up to about 20 for subsets, a target of a few dozen for sums.

The near-misses. Order matters, so [1, 2] and [2, 1] are different answers: that's permutations, the next lesson (Backtracking: Permutations and Partitions). Only a count, or only yes or no, with a large input: the number of different situations is small even when the tree is huge, so remember them instead (Knapsack: Subsets, Sums and Coins).

When it breaks. Check if there exists a subsequence with sum K allows 2,000 values. The search above, asked about values that can never hit the target, took 28 ms for 16 values, 111 ms for 18 and 1,794 ms for 22: each extra value doubles it, and 2,000 values are beyond any machine. But a yes/no about a sum only depends on where you are and how much is left, at most n × k different situations, so a table answers it: that's dynamic programming, not backtracking.

Bugs that cost a submission

Storing the path instead of a copy.

def subsets(nums):
    out, path = [], []

    def take_or_skip(i):
        if i == len(nums):              # every value decided: one subset
            out.append(path)            # the list itself
            return
        path.append(nums[i])            # choose: take nums[i]
        take_or_skip(i + 1)             # explore
        path.pop()                      # unchoose
        take_or_skip(i + 1)             # and the other branch: skip it

    take_or_skip(0)
    return out

subsets([1, 2]) returned [[], [], [], []]: four references to the same list, which is empty once the search ends. Store path[:] (new ArrayList<>(path) in Java, [...path] in JavaScript; C++'s push_back already copies).

i > 0 instead of i > start.

            if i > 0 and nums[i] == nums[i - 1]:
                continue

On [1, 2, 2] it returned [[], [1], [1, 2], [2]], without [1, 2, 2] or [2, 2]. It skips the second 2 even in a deeper call, where it's the only way to use two 2s.

i + 1 in Combination Sum.

            fill(i + 1, left - candidates[i])

On [2, 3, 6, 7] and 7 it returned [[7]], losing [2, 2, 3]: moving on after every pick means no number is used twice.

Cutting before sorting.

def combination_sum(candidates, target):
    out, path = [], []      # no sort
    ...

On [3, 8, 2] and 5 it returned []; sorted, [[2, 3]]. After taking 3, the loop meets 8, too big, and stops, never reaching the 2 behind it. The break is only safe when every later candidate is at least as big.

Check yourself

Quiz

1 / 6

Multiple choice

How many calls does the take-or-skip code make on 4 values?

Practice problems

In this order:

Generate all binary strings: take or skip, written as 0 or 1.
Understanding Subsequences: every subsequence of a string, the same tree.
Subsets: the template.
Subset Sums: the same tree, a sum at each leaf.
Subsets II: sort, and skip equal values at one depth.
Combinations: stop at k values, and cut when too few are left.
Letter Combinations of a Phone Number: one level per digit.
Combination Sum: reuse with i, cut with break.
Combination Sum II: each copy once, repeats skipped.
Combination Sum III: k digits from 1 to 9.
Generate Parentheses: two counts decide each step.
Check if there exists a subsequence with sum K: small inputs by search; at 2,000 values, a table.

Next, Backtracking: Permutations and Partitions: when order matters.