One shared vector, pushed before every call and popped after it.
Backtracking is a tree walk where the tree is every decision you could make. Each box is one call, labelled with what cur holds when it starts. Watch the cur strip: it grows on the way down and shrinks on the way back, so every branch starts from the same state. LC 77 compares three versions of one solution by how many calls they waste.
Press Next to make the first call.
Include / exclude asks one yes-or-no question per level: is nums[start] in? Every element doubles the paths, so there are 2n leaves, and a subset is only recorded at a leaf, once every element has been decided. The tree has 2n+1 − 1 calls.
For loop from start asks a different question: which element comes next? Every box is already a subset, so it is recorded as soon as the call starts, and the tree has exactly 2n calls. Recursing with i + 1 means only later elements can follow, which is why [2, 1] never appears. LC 77, 39, 40 and 90 all reuse this shape.
Whatever a call pushes, it pops before it returns.
Combinations are LC 78's for-loop tree keeping only one layer, the subsets of size k. Pick first: no return: the call records a full cur and then keeps pushing, so the whole subsets tree is walked and most of it is wasted. + return when full cuts everything below a full cur. + pruning also refuses to start a branch that can't reach k: with need numbers missing, i stops at n − need + 1. Try n = 5, k = 4, where the return alone saves little and the pruning saves most.
One level per digit, one branch per letter, so the tree is exactly digits.size() deep and every leaf records. There's nothing to prune: no branch can fail. Try "79", where both keys have four letters: 16 leaves, 16 answers, 21 calls, and not one wasted.
Subsets and combinations recursed with i + 1 so only later numbers could follow, which is why [2, 1] never appeared. In a permutation it must, so each level loops over all of nums, and the used strip is what stops a number being picked twice. Choosing now changes two pieces of shared state, so both are undone after the call. The tree has n · (n − 1) · … · 1 = n! leaves, every one an answer; the skipped slots, shown in red on the used strip, are the only extra work.
Each candidate can be reused, so after choosing one the call recurses from the same index: a +2 can be followed by another +2, but never by anything earlier, so [2, 3, 2] is never built. Nothing runs out, so the shrinking target is what ends each branch; it's shown in each box. A branch whose remaining target no candidate fits is a dead end. Try [3, 5], target 9: only [3, 3, 3] works, and the dead ends show where the search gave up.
cur is passed by reference, so every call writes into the same vector, as ans did in Week 2's traversals. After exploring the branch with an element, the next branch must not still contain it. pop_back undoes the choice, and the strip shows cur back where it was before the push. Leave it out and leftovers from one branch leak into every branch after it.