SG
← Back

Backtracking Introduction

Build candidate solution incrementally and abandon dead branches. Backtracking is a problem-solving algorithm that explores all possible configurations by building solutions step-by-step, removing invalid paths early to optimize search.

recursionbacktrackingUpdated 2025-09-01

Explanation in Simple Terms

  • Backtracking is like trying different paths in a maze: you take a step forward (choose an option), explore further (recurse), and if you hit a dead end, you step back (unchoose) and try another way.
  • It's built on recursion, where you make choices incrementally to build a solution, and prune branches that can't lead to a valid answer.
  • Real-life example: Planning a road trip with multiple stops. You choose a route to the first stop, then the next, but if a road is blocked (invalid), you backtrack to the last choice and pick a different path. This avoids exploring impossible routes entirely.

Template

  • The basic structure: choose an option → explore the next step (recurse) → unchoose if it doesn't work (backtrack).
  • In code, it's often a recursive function with a base case for valid/invalid solutions, a loop to try choices, and cleanup after recursion.

C++ Basics for Backtracking

  • Backtracking in C++ uses recursion, vectors for tracking solutions, and boolean checks for validity.
  • Key concepts: Use a recursive function. Pass current state (e.g., a vector building the solution). Use a loop to try each possible choice. Add choice, recurse, then remove (backtrack).

  • Simple C++ skeleton:

    #include <bits/stdc++.h>
using namespace std;

void backtrack(vector<int>& current, int n) {
    // Base case: if solution is complete
    if (current.size() == n) {
        // Process solution
        return;
    }
    for (int choice = 1; choice <= n; ++choice) {
        // Check if choice is valid
        if (/* valid */) {
            current.push_back(choice);  // Choose
            backtrack(current, n);      // Explore
            current.pop_back();         // Unchoose
        }
    }
}

Example Problem: Generate All Subsets of a Set

  • Problem: Given a set like {1, 2, 3}, generate all possible subsets (including empty).
  • This is understandable for beginners: Subsets are combinations, and backtracking builds them by choosing to include or exclude each element.

  • C++ Code Example:

    #include <bits/stdc++.h>
using namespace std;

void generateSubsets(vector<int>& nums, vector<int>& current, int index, vector<vector<int>>& result) {
    // Base case: reached end of nums
    if (index == nums.size()) {
        result.push_back(current);
        return;
    }
    // Choice 1: Exclude current element
    generateSubsets(nums, current, index + 1, result);
    // Choice 2: Include current element
    current.push_back(nums[index]);
    generateSubsets(nums, current, index + 1, result);
    current.pop_back();  // Backtrack
}

int main() {
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> result;
    vector<int> current;
    generateSubsets(nums, current, 0, result);
    // Output subsets
    for (auto& subset : result) {
        cout << '{';
        for (int num : subset) cout << num << ' ';
        cout << '}' << endl;
    }
    return 0;
}

Output:
{}
{3}
{2}
{2 3}
{1}
{1 3}
{1 2}
{1 2 3}

Use Cases

  • N-Queens (placing queens on chessboard without attacks)
  • Permutations (all arrangements of items)
  • Sudoku (filling grid with constraints)

Practice Problems

  • 1. Generate all permutations of a string. Hint: Use backtracking to swap characters and recurse.
  • 2. Solve the N-Queens problem for N=4. Hint: Track queen positions in rows, check diagonals and columns for attacks.
  • 3. Subset Sum: Find subsets that sum to a target. Hint: Similar to subsets, but add sum check in base case.

Quiz to Test Understanding

  • Question 1: What is the purpose of 'unchoose' in backtracking? (A) To add more options (B) To remove a choice after exploring (C) To skip recursion
  • Answer: B
  • Question 2: In the subset example, why do we have two recursive calls? (A) One includes, one excludes (B) For duplicates (C) To sort
  • Answer: A
  • Question 3: Can backtracking solve Sudoku? Why? (Short answer)
  • Answer: Yes, by trying numbers in cells, checking validity, and backtracking on conflicts.