Backtracking
Explore every possible solution by making a choice, recursing, and undoing the choice: permutations, subsets with a target sum, n queens, and how pruning makes exponential searches practical.
Choose: add one option to the partial solution. Explore: recurse to make the next choice. Un-choose: remove that option again, so the next option starts from a clean state.
var crews = new[] { "Asha", "Bala", "Chen" };var current = new List<string>();var used = new bool[crews.Length];Permute(); void Permute(){ if (current.Count == crews.Length) // a complete order { Console.WriteLine(string.Join(" → ", current)); return; } for (int i = 0; i < crews.Length; i++) { if (used[i]) continue; used[i] = true; current.Add(crews[i]); // choose Permute(); // explore current.RemoveAt(current.Count - 1); // un-choose used[i] = false; }}Asha → Bala → Chen Asha → Chen → Bala Bala → Asha → Chen Bala → Chen → Asha Chen → Asha → Bala Chen → Bala → Asha
Pruning: n queens
for (int n = 1; n <= 8; n++) Console.Write($"{n}:{CountQueens(n)} "); static int CountQueens(int n){ var cols = new bool[n]; var diag1 = new bool[2 * n]; // r + c is the same along one diagonal var diag2 = new bool[2 * n]; // r − c is the same along the other return Place(0); int Place(int r) { if (r == n) return 1; // all rows filled: one solution int count = 0; for (int c = 0; c < n; c++) { if (cols[c] || diag1[r + c] || diag2[r - c + n]) continue; // attacked: prune cols[c] = diag1[r + c] = diag2[r - c + n] = true; // choose count += Place(r + 1); // explore cols[c] = diag1[r + c] = diag2[r - c + n] = false; // un-choose } return count; }}1:1 2:0 3:0 4:2 5:10 6:4 7:40 8:92
bool arrays answer “is this square attacked?” in O(1) instead of checking every queen. Fast checks and early pruning are what separate a backtracking solution that finishes in milliseconds from one that runs for hours.
Subsets with a target sum
int[] pieces = { 2, 3, 5, 7 }; // sorted ascendingvar pick = new List<int>();Find(0, 10); void Find(int start, int remaining){ if (remaining == 0) { Console.WriteLine(string.Join(" + ", pick)); return; } for (int i = start; i < pieces.Length; i++) { if (pieces[i] > remaining) break; // prune: every later piece is longer still pick.Add(pieces[i]); // choose Find(i + 1, remaining - pieces[i]); // explore (each piece used at most once) pick.RemoveAt(pick.Count - 1); // un-choose }}2 + 3 + 5 3 + 7
Where backtracking is used
Puzzles: sudoku, crosswords, n queens. Combinatorial search: all subsets, combinations or orders that satisfy some rules. Constraint problems: timetables, shift rosters, assigning crews to tasks with restrictions. Parsing and pattern matching (regular expression engines backtrack).
((())), (()()), (())(), ()(()), ()()().
Show a hint
( while fewer than n are open in total, and ) while it would close an open one (closed < opened). When the length is 2n, print it.
Show the solution
var sb = new System.Text.StringBuilder();Build(0, 0, 3); void Build(int open, int close, int n){ if (sb.Length == 2 * n) { Console.WriteLine(sb); return; } if (open < n) { sb.Append('('); Build(open + 1, close, n); sb.Length--; // un-choose } if (close < open) { sb.Append(')'); Build(open, close + 1, n); sb.Length--; }}((())) (()()) (())() ()(()) ()()()
Remember
Backtracking = choose, explore, un-choose: DFS over partial solutions. It is exponential; pruning invalid branches early is what makes it practical. Fast validity checks (like the diagonal arrays in n queens) matter as much as the pruning itself. If identical subproblems repeat, switch to dynamic programming.