Recursion and Backtracking

Recursion and exhaustive search: subsets, permutations and the tree of choices.

Recursion is a function that calls itself. Correct recursion always has two ingredients: a base case (when to stop) and a step (how to reduce the problem to a smaller one). Its main contest application is exhaustive search: systematically visiting ALL possibilities. For example, all subsets of a set: for each element there are two choices — take it or not. You get a tree of choices of depth n with 2ⁿ leaves.

Try it yourself — the code is editable

Input (sample — feel free to edit)

All subsets. Enter: 3, then 1 2 3

The line current.pop_back() is the heart of the technique called backtracking: make a choice, explore the branch, UNDO the choice and try the next one. A forgotten undo is mistake number one in search code. Get a feel for the scale: 2ⁿ subsets — search is realistic up to n ≈ 20-25. Permutations are even more numerous: n! (at n = 10 that is already 3.6 million). For permutations C++ has a ready-made next_permutation.

Try it yourself — the code is editable

Input (sample — feel free to edit)

All permutations of a string. Enter: abc

When the full search is too big, pruning saves you: don't enter a branch that provably cannot yield an answer. A smart search with pruning solves problems where the brute-force way would take forever. Task: print all ways to place + and - signs between the numbers 1 2 3 4 so that the result equals zero (searching 2³ sign choices). Mark the lesson as completed and move on to greedy algorithms.