What is backtracking?

Backtracking is a systematic way to explore all candidate solutions by building one incrementally and undoing the last step when a branch is finished or fails. It is a depth-first search over a tree of choices: at each node you make a choice, recurse, and then pop that choice to try the next one. The push-recurse-pop rhythm visits every valid partial solution exactly once.

How does backtracking generate all subsets?

Treat each element as a decision. Starting from an index, you add an element, record the current path as a subset, recurse on the remaining elements, then pop that element and move on to the next candidate. Because every node in this decision tree corresponds to a distinct subset, visiting the whole tree yields all two-to-the-n subsets of the set.

Subsets versus permutations by backtracking?

Both use the same push-recurse-pop skeleton but branch differently. For subsets you decide include-or-skip for each element from a moving start index, so order does not matter and there are 2^n of them. For permutations you place every remaining element in the next position, so order matters and there are n! of them. Passing a start index prevents subsets from producing reordered duplicates.

Algorithm · Backtracking

Push, Recurse, Pop.

Q: How many subsets does a set of n elements have?

Exactly two to the power n. Each element is independently either in or out of a subset, giving 2 times 2 times ... = 2^n combinations, including the empty set and the full set. Generating all of them therefore costs at least O(2^n), and O(n · 2^n) if you copy each subset out, since a subset can hold up to n elements.

Don't memorize backtracking — watch the decision tree grow and unwind. To list every subset of a set, treat each element as a choice: take it or skip it. Every node you land on is a subset, and the moment a branch runs out you pop the last choice and try the next. That push-recurse-pop rhythm is the whole of backtracking — the engine behind subsets, permutations, N-Queens and Sudoku.

decision tree · every node is a subset · pop to undo · 2ⁿ leaves

BACKTRACK

Build a choice step by step; undo the last step when the branch is done.

DECISION TREE

At each element you branch: include it, or move past it. A tree of partial answers.

EVERY NODE COUNTS

For subsets, each node you visit is itself a valid subset — record it.

POP TO UNDO

After a branch, remove the last element (path.pop()) and try the next candidate.

subsets.sim — all subsets of {1, 2, 3}

Ready

Each node is a subset. From a node you branch to add the next larger element. Press Step to walk the tree depth-first — every node visited is recorded, and finishing a branch pops back to try the next.

bt(start, path): record path; for i in start..n: push, bt(i+1), pop

Subsets found

∅

Current path

The tree is the algorithm

Backtracking is just depth-first search over a tree you never actually build — you generate it on the fly with the call stack. For subsets, the rule at each step is: from the current position, pick the next element to include, recurse on everything after it, then remove it. That moving start index is the key detail: by only ever looking forward, you generate each subset once, in a tidy order, and never produce a reshuffle of one you already have. Every recursive call corresponds to a node, and because a subset is the path from the root, you record the path at the top of every call. Two-to-the-n nodes, two-to-the-n subsets.

Record the node

At the start of each call, the current path is a complete subset — push a copy into the results.

Branch forward

Loop i from start to n−1: choose to include element i by pushing it onto the path.

Recurse deeper

Call bt(i + 1, path) — later choices can only use elements after i, so no duplicates.

Pop and continue

path.pop() undoes the choice; the loop moves to the next i. That pop is the backtrack.

Subsets

2ⁿ

Time

O(n · 2ⁿ)

Space

O(n)

Pattern

Backtracking

Change only the branching rule and the same skeleton solves a whole family of problems. Place every remaining element in the next slot and you get permutations (n! of them). Add a constraint check before recursing — no two queens attacking, a legal Sudoku digit, a running sum that has not overshot a target — and you get N-Queens, Sudoku, combination sum. The wins come from pruning: cut a branch the instant it cannot lead to a solution, and the 2ⁿ or n! blow-up shrinks dramatically.

Check yourself

1 · How many subsets does a set of n elements have?

Every element is a yes/no choice, so there are 2 × 2 × … = 2ⁿ subsets, including the empty set and the full set.

2 · In backtracking, what does the "backtrack" step actually do?

After exploring a branch you pop the last element off the path, returning to the parent state so the next candidate can be tried.

3 · Why recurse with a moving start index (i + 1)?

Only looking forward means {1,2} is generated but never {2,1}; subsets are order-free, so this avoids duplicates.

Questions

Subsets vs permutations — same code?

Same push-recurse-pop skeleton, different branching. Subsets decide include-or-skip from a moving start index (order-free, 2ⁿ). Permutations place each unused element into the next position (order matters, n!). Swap the loop and you switch problems.

Could I just use bitmasks instead?

For plain subsets, yes: iterate a counter from 0 to 2ⁿ−1 and read its bits as include flags. Backtracking earns its keep when you need to prune — skip whole branches that violate a constraint — which a flat bitmask loop cannot do.

Why is it O(n · 2ⁿ), not O(2ⁿ)?

There are 2ⁿ subsets, but copying each one into the results costs up to n (a subset can hold all n elements). Multiply and you get O(n · 2ⁿ) work overall.

One rhythm, a whole family of problems.

Push a choice, recurse, pop it back. Change the branch rule and add pruning — subsets become permutations, N-Queens, Sudoku.

← All algorithms N-Queens → DFS → Big-O Cheatsheet →

Finished this one? 0 / 47 Algorithms done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA

Push, Recurse, Pop.

The tree is the algorithm

Record the node

Branch forward

Recurse deeper

Pop and continue

Check yourself

Questions

One rhythm, a whole family of problems.

Explore the topic

More Algorithms

Explore more from Vibe Engines

The tree is the algorithm

Record the node

Branch forward

Recurse deeper

Pop and continue

Check yourself

Questions

One rhythm, a whole family of problems.

Explore the topic

More Algorithms

Explore more from Vibe Engines

Get the next one in your inbox.