Interactive Lab · DSA & Algorithms
Every “generate all…” interview problem is the same three-line dance. Choose an option and add it to the path, explore everything that follows by recursing, then un-choose it (pop it off) and try the next option. Done this way, the calls trace out a recursion tree, and the size of that tree is the running time: 2n nodes for subsets, about n! for permutations. The trick that separates a pass from a TLE is pruning: noticing a branch can never succeed and cutting it before it grows. Watch the tree grow, then flip pruning on and watch the node counter collapse.
▶ The playground, grow the recursion tree one call at a time
The faint grey tree is every call this search will make. Each step makes one move: a choose walks down an edge (the edge label is the element added), an un-choose walks back up. The blue path is exactly the call stack, and the chips below are the path list at that moment.
Backtracking is the template behind a whole column of the interview sheet: Subsets, Permutations, Combination Sum, Letter Combinations, Palindrome Partitioning, Word Search, Sudoku and N-Queens. Outside interviews it powers constraint solvers (SAT, timetabling, register allocation) and puzzle engines. Whenever an answer is a sequence of choices, draw the recursion tree first, its size is your complexity, and your pruning rule is your optimisation.
The code that's actually running, the backtracking template
Pick Permutations, set n = 5 and untick prune. Without the used check, the search tries every element at every level and only rejects duplicates at the bottom, so it reaches 55 = 3125 leaves. Predict: with pruning back on, how many leaves are left? Only the real permutations survive, 5! = 120, and the total node count drops from 3,906 to 326. Then switch to target sum with n = 6 and flip prune on and off: the answers never change, only the wasted work does.
The takeaway
path.append(x), recurse, path.pop(). The pop is what lets one list serve the whole search, it restores the state for the next sibling.2n nodes. Permutations: n choices, then n−1, then n−2… roughly n! leaves. Count the tree and you have the complexity.sum + nums[i] > target every later candidate overshoots too, so you break the loop and cut all remaining siblings.