Backtracking explained
How backtracking searches every possibility with choose, explore and un-choose, with subsets, permutations, N-Queens and pruning.
Backtracking builds a solution one choice at a time. After each choice it recursively explores everything that follows, then undoes the choice and tries the next one. It's a depth-first walk through a tree of decisions, and every backtracking function has the same three moves:
- Choose: change the state (push a value, place a queen, mark a cell).
- Explore: recurse to make the next choice.
- Un-choose: put the state back exactly as it was, so the next option starts clean.
Exhaustive search grows fast (n items have 2ⁿ subsets and n! orderings), so pruning matters: as soon as a partial choice can't lead to a valid answer, stop exploring that branch. That's what makes N-Queens, Sudoku and word-search solvers fast in practice.
When the same sub-question keeps coming up during the search, switch to dynamic programming and store its answer.
Example
#include <iostream>
#include <vector>
void subsets(const std::vector<int>& v, std::size_t i, std::vector<int>& cur) {
if (i == v.size()) {
std::cout << "{";
for (std::size_t k = 0; k < cur.size(); k++) std::cout << (k ? " " : "") << cur[k];
std::cout << "} ";
return;
}
cur.push_back(v[i]); // choose: take v[i]
subsets(v, i + 1, cur); // explore
cur.pop_back(); // un-choose
subsets(v, i + 1, cur); // the other branch: skip v[i]
}
int main() {
std::vector<int> cur;
subsets({1, 2, 3}, 0, cur);
std::cout << "\n";
return 0;
}
Output:
{1 2 3} {1 2} {1 3} {1} {2 3} {2} {3} {}