Backtracking

Listing every subset of a 20-element set produces over a million results, and there is no shortcut: you have to enumerate them. The trick is to do it without writing 20 nested loops. Backtracking solves the entire family of "generate all configurations" problems with a single recursive template that walks an implicit decision tree. **Backtracking (Intro)** introduces that template as the "choose, explore, unchoose" pattern. You will see how each recursive frame picks an option, recurses into the resulting state, and then undoes the choice on the way back up so the next branch starts from a clean slate. Classic problems include generating all subsets and permutations, the N-Queens placement puzzle, and a first look at Sudoku. The lesson also introduces pruning, where invalid partial solutions are cut off early so the algorithm explores far less than the full `O(2^n)` or `O(n!)` worst case. In **Recursion Fundamentals**, you learned to define a problem in terms of smaller subproblems. Backtracking adds one more idea: state mutated during recursion has to be restored before returning, so siblings in the call tree see the same starting state. From here, **BFS & DFS (Intro)** generalizes the same tree-of-states view to actual graphs.

0/1 Knapsack is exponentially many subsets to consider, but commercial solvers like CPLEX and Gurobi answer instances with thousands of items in seconds. The trick is not better hardware but smarter exploration: at every node of the search tree, compute a cheap upper bound on what any completion of the partial solution could possibly achieve, and prune the entire subtree if that bound cannot beat the best solution found so far. That single discipline of provably-suboptimal pruning is what defines branch and bound. **Branch and Bound** introduces the framework as a refinement of backtracking. You will design bounding functions (typically a relaxation, like fractional knapsack as a bound for 0/1 knapsack), build state-space trees, and choose between three exploration strategies: FIFO (BFS-like), LIFO (DFS-like), and least-cost (priority queue). Classic applications include 0/1 Knapsack with the fractional-relaxation bound, the Traveling Salesman Problem, and the job-assignment problem. The lesson also draws the line between B&B and DP so you know when each is the right approach. In **Backtracking (Intro)**, you walked an implicit decision tree with choose, explore, unchoose. **Greedy (Intro)** taught you that locally optimal choices sometimes give global optima. Branch and bound borrows the search structure of one and the bounding intuition of the other. Next, **Divide and Conquer (Advanced)** turns to algebraic D&C tricks like Karatsuba and Strassen.