Build, recurse, undo
Backtracking is depth-first search over partial candidates. You extend the current partial solution by one choice, recurse, and on the way back out you undo exactly that choice so the next sibling branch sees the state it expects. The undo is the part people skip, and skipping it does not usually produce a crash; it produces output that is subtly wrong in ways that only appear a few branches in.
For permutations the partial candidate is a prefix, and the choice at each level is which unused element goes next. A used flag array is the natural representation because the alternative, swapping elements in place, mutates the ordering that the duplicate-skip below relies on.
void permute(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> out) {
if (path.size() == nums.length) {
out.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
used[i] = true;
path.add(nums[i]);
permute(nums, used, path, out);
path.remove(path.size() - 1);
used[i] = false;
}
}
Sort nums before the first call or the skip is meaningless, since it only compares adjacent positions. The condition deserves a sentence out loud rather than being pasted: among the identical copies of a value, only the leftmost unused one may be chosen at any level, which fixes a single canonical order per multiset and so emits each distinct permutation exactly once. Invert the condition to used[i - 1] and you get the opposite convention, which also happens to work; drop it and you get k! copies of every permutation containing a value repeated k times.
Subsets look similar but the skip differs, and it differs for a reason worth stating. There the loop starts at an index rather than at zero, so all copies of a value are considered at the same level, and the correct condition is i > start && nums[i] == nums[i - 1]. The change from i > 0 to i > start is not cosmetic: it allows a duplicate to be picked when it is the first candidate at this level, which is how [2, 2] gets generated at all.
Counting the tree honestly
Cost is nodes visited multiplied by work per node, and for these problems both halves matter.
The subset tree is a binary decision tree over n elements, so it has 2^n leaves and 2^(n+1) - 1 nodes. Per-node work is constant except for the snapshot, and a snapshot averages n/2 elements, giving O(n · 2^n) time and O(n) auxiliary space beyond the output.
For permutations, the number of nodes at depth k is the number of ordered k-prefixes, n!/(n-k)!. Summing over all depths gives n! · Σ 1/j! for j from 0 to n, which is bounded by e · n!. So the internal nodes contribute only a constant factor over the leaves, the leaf count dominates, and with the O(n) copy the total is O(n · n!). That bound is also the output size, so no cleverness in the recursion improves it — you can only avoid the copy by streaming instead of collecting.
Pruning near the root versus pruning at the leaves
The useful mental model is that a cut at depth k deletes a subtree, and the subtree's size is what you saved. Rejecting an invalid candidate only once it is complete saves nothing asymptotically, because you already paid to walk down to it. Rejecting at depth 1 in an n-level permutation tree removes (n-1)! leaves in one test.
N-Queens is the clean illustration. Placing queens row by row and checking the full board only at row n explores every one of the n! column assignments. Testing attack constraints as you place removes a whole subtree the moment two queens conflict, and it happens to encode in three integers:
This is still exponential. Pruning changed the base of the exponent, not the fact of it, and the difference between "N-Queens is fast now" and "N-Queens is tractable to about n in the low thirties" is the sort of overclaim an interviewer will test by asking for n = 30. Say which one you mean.
Quote the cost as nodes times per-node work, and when you add a prune, say which subtree it deletes and how big that subtree was. A prune you cannot size is a prune you cannot defend.
© 2026 Preptima. Originally published at preptima.com (opens in a new tab).