Backtracking

// Try every candidate for the next choice
for (auto& candidate : getCandidates(state)) {
    if (!isValid(state, candidate)) continue; // prune invalid
    
    makeChoice(state, candidate);             // CHOOSE
    backtrack(state, results);                // EXPLORE
    undoChoice(state, candidate);             // UN-CHOOSE
}

}

</div>
<h3>1.1 — Backtracking vs Brute Force vs DP</h3>
<div class="table-responsive">
<table class="insight-table">
<thead>
<tr>
<th>Dimension</th>
<th>Brute Force</th>
<th>Backtracking</th>
<th>Dynamic Programming</th>
</tr>
</thead>
<tbody>
<tr>
<td><strong>Exploration</strong></td>
<td>All possible states</td>
<td>Prune invalid subtrees early</td>
<td>Reuse stored subproblem results</td>
</tr>
<tr>
<td><strong>When used</strong></td>
<td>No known structure</td>
<td>Constraint-based search</td>
<td>Overlapping subproblems</td>
</tr>
<tr>
<td><strong>Undo step</strong></td>
<td>Not needed</td>
<td>Required (un-choose)</td>
<td>Not needed</td>
</tr>
<tr>
<td><strong>Complexity</strong></td>
<td>Worst case exponential</td>
<td>Exponential but pruned</td>
<td>Polynomial (with memoisation)</td>
</tr>
<tr>
<td><strong>Output type</strong></td>
<td>One optimal value</td>
<td>All valid solutions (or one)</td>
<td>One optimal value</td>
</tr>
<tr>
<td><strong>Space</strong></td>
<td>O(1) extra</td>
<td>O(depth) recursion stack</td>
<td>O(n) to O(n²) table</td>
</tr>
<tr>
<td><strong>Classic problems</strong></td>
<td>Loop over all subsets</td>
<td>Subsets, Permutations, N-Queens</td>
<td>Coin Change, LCS, Knapsack</td>
</tr>
</tbody>
</table>
</div>
<div class="insight-box idea">
<h4>Real-World Analogy: Solving a Maze</h4>
<p>You stand at the entrance of a maze and want to find the exit. At each junction, you try one path. If you hit a dead end, you backtrack to the last junction and try a different path. This is exactly backtracking: explore a path fully, and if it fails, undo your steps and try the next option.<br><br><strong>Pruning:</strong> if a corridor is blocked (invalid constraint), skip it immediately without entering.<br><strong>The maze metaphor maps to code:</strong> junction = recursive call, dead end = base case failure, backtrack = undo the last choice.</p>
</div>
</section>
<!-- SECTION 2 -->
<section id="section-2" class="chapter-section">
<h2> 2 — Visual Diagrams: Decision Trees</h2>
<h3>Diagram 1 — Subsets Decision Tree</h3>
<p><strong>Subsets: Full Decision Tree (n=3)</strong><br><code>nums = [1, 2, 3]</code><br>Generate all subsets (power set). At each level, we decide: include <code>nums[i]</code> or skip it.</p>
<pre class="trace-output">
                  []
               /      \
            [1]         []
           /   \       /  \
        [1,2]  [1]   [2]   []
        /  \   / \   / \   / \
[1,2,3][1,2][1,3][1][2,3][2][3][]
</pre>
<p>Leaves (all 8 = 2³ subsets): <code>[1,2,3] [1,2] [1,3] [1] [2,3] [2] [3] []</code><br>No pruning needed here (all paths are valid). Total nodes in tree = 2^(n+1) - 1 = 15 for n=3.</p>
<h3>Diagram 2 — Permutations Decision Tree</h3>
<p><strong>Permutations: Decision Tree (n=3)</strong><br><code>nums = [1, 2, 3]</code><br>Generate all permutations. At each level, pick one unused number. <code>used = {}</code> tracks which numbers are already in the current path.</p>
<pre class="trace-output">
                []
          /      |      \
        [1]     [2]     [3]
       /   \    /  \    /  \
    [1,2][1,3][2,1][2,3][3,1][3,2]
      |     |    |    |    |    |
[1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1]
</pre>
<p>6 leaves = 3! = n! permutations. No pruning (no duplicates in input). Total nodes = 1 + 3 + 6 + 6 = 16 for n=3.<br><em>With duplicates (e.g. [1,1,2]):</em> sort first, then skip if <code>nums[i] == nums[i-1]</code> and <code>nums[i-1]</code> was <strong>NOT</strong> used in this level. This prunes duplicate branches at each depth level.</p>
<h3>Diagram 3 — N-Queens Pruning</h3>
<p><strong>N-Queens: Constraint-Based Pruning</strong><br>N=4: place 4 queens on a 4x4 board, no two attacking each other. Place one queen per row. For each row, try all columns.</p>
<pre class="trace-output">
Row 0: try col 0, 1, 2, 3.
Row 0, col 0:
Q . . .
 
Row 1, try cols:
col 0 (same col, PRUNE), col 1 (diagonal, PRUNE), col 2 (safe), col 3 (diagonal, PRUNE).
 
Row 1, col 2:
Q . . .
. . Q .
 
Row 2, try cols:
all attacked by Q at (0,0) or (1,2) -> all PRUNED. Backtrack to row 1.
 
Try col 3:
Q . . .
. . . Q
 
Row 2, col 1:
Q . . .
. . . Q
. Q . .
 
Row 3: cols 0 (col prune), 1 (col prune), 2 (diag prune), 3 (col prune). 
All pruned. Backtrack to row 0, try col 1.  ...
</pre>
<p><strong>Solutions found: 2 (for N=4).</strong></p>
<pre class="trace-output">
. Q . .      . . Q .
. . . Q      Q . . .
Q . . .      . . . Q
. . Q .      . Q . .
</pre>
<p><strong>Pruning criteria:</strong> same column, same diagonal (r1-c1 == r2-c2), or same anti-diagonal (r1+c1 == r2+c2).</p>
<h3>Diagram 4 — Combination Sum</h3>
<p><strong>Combination Sum: Pruning on Remaining Target</strong><br><code>candidates = [2, 3, 6, 7]</code>, <code>target = 7</code><br>Find all combinations that sum to target (reuse allowed).</p>
<pre class="trace-output">
start=0 (index), path=[], remaining=7
 |
 +-- pick 2, remaining=5
 |     +-- pick 2, remaining=3
 |     |     +-- pick 2, remaining=1
 |     |     |     +-- pick 2, remaining=-1 PRUNE (negative)
 |     |     |     +-- pick 3, remaining=-2 PRUNE
 |     |     +-- pick 3, remaining=0   SOLUTION: [2,2,3]
 |     |     +-- pick 6, remaining=-3 PRUNE
 |     +-- pick 3, remaining=2
 |     |     +-- pick 3, remaining=-1 PRUNE
 |     |     (no more valid picks)
 |     +-- pick 6, remaining=-1 PRUNE
 +-- pick 3, remaining=4
 |     +-- pick 3, remaining=1
 |     |     +-- pick 3, remaining=-2 PRUNE
 |     +-- pick 6, remaining=-2 PRUNE
 +-- pick 6, remaining=1
 |     +-- pick 6, remaining=-5 PRUNE
 +-- pick 7, remaining=0   SOLUTION: [7]
</pre>
<p>Solutions: <code>[2,2,3]</code> and <code>[7]</code>.</p>
</section>
<!-- SECTION 3 -->
<section id="section-3" class="chapter-section">
<h2> 3 — Real-World Use Cases</h2>
<div class="table-responsive">
<table class="insight-table">
<thead>
<tr>
<th>Problem</th>
<th>Backtracking Application</th>
<th>Industry System</th>
</tr>
</thead>
<tbody>
<tr>
<td>Puzzle solving</td>
<td>Sudoku, crosswords, constraint satisfaction</td>
<td>Game engines, puzzle generators</td>
</tr>
<tr>
<td>Circuit layout</td>
<td>VLSI routing — place wires avoiding conflicts</td>
<td>EDA (Electronic Design Automation) tools</td>
</tr>
<tr>
<td>Regex matching</td>
<td>NFA simulation backtracks on failed matches</td>
<td>grep, database query engines, parsers</td>
</tr>
<tr>
<td>Natural language parsing</td>
<td>Earley/CYK parser explores grammar rules</td>
<td>NLP compilers, syntax highlighters</td>
</tr>
<tr>
<td>Test case generation</td>
<td>Enumerate all input combinations for coverage</td>
<td>Automated software testing frameworks</td>
</tr>
<tr>
<td>Scheduling</td>
<td>Assign tasks to slots satisfying constraints</td>
<td>University timetabling, exam scheduling</td>
</tr>
<tr>
<td>Cryptography</td>
<td>Key space enumeration for brute-force attacks</td>
<td>Security penetration testing tools</td>
</tr>
<tr>
<td>Combinatorial optimisation</td>
<td>TSP branch-and-bound with backtracking pruning</td>
<td>Logistics, route planning, supply chain</td>
</tr>
<tr>
<td>AI game playing</td>
<td>Minimax with alpha-beta pruning</td>
<td>Chess engines, Go AI (pre-neural era)</td>
</tr>
</tbody>
</table>
</div>
</section>
<!-- SECTION 4 -->
<section id="section-4" class="chapter-section">
<h2> 4 — Core Concepts & Algorithms</h2>
<h3>4.1 — Subsets (Power Set)</h3>
<p>Generate all 2^n subsets of nums. The start index prevents permutations of the same subset.</p>
<div class="ch-code-wrap">
```cpp
// LeetCode 78 — Subsets — O(2^n * n) Time, O(n) Space
class Solution {
    void bt(vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& res) {
        res.push_back(path); // every node is a valid subset
        
        for (int i = start; i < (int)nums.size(); i++) {
            path.push_back(nums[i]);       // CHOOSE
            bt(nums, i+1, path, res);      // EXPLORE (i+1: no reuse)
            path.pop_back();               // UN-CHOOSE
        }
    }
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> path;
        bt(nums, 0, path, res);
        return res;
    }
};

// Subsets II — with duplicates (LC 90)
// Sort first, then skip nums[i] == nums[i-1] at the same recursion level.
void btII(vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& res) {
    res.push_back(path);
    for (int i = start; i < (int)nums.size(); i++) {
        if (i > start && nums[i] == nums[i-1]) continue; // skip duplicate
        path.push_back(nums[i]);
        btII(nums, i+1, path, res);
        path.pop_back();
    }
}