Recursion and Backtracking Questions

Situation: In your code review I saw a recursive backtracking solution that produced incorrect outputs and poor performance because a single mutable result list was shared incorrectly across recursion branches and there was no pruning of impossible branches.

Feedback (constructive, actionable):

• Bug: The shared list is mutated by multiple branches without proper backtracking (append/pop) or copying, causing results to leak between branches.
• Performance: No pruning means you explore subtrees that cannot lead to valid solutions.
• Style: Add clear invariants in comments and small helper functions to encapsulate recursion state.

Suggested code changes (Python example):

def backtrack(path, choices, results):
    # path is mutated but we undo changes (backtrack) after recursion
    if is_solution(path):
        results.append(list(path))  # append a copy to avoid aliasing
        return
    for c in choices_for(path):
        if should_prune(path, c):  # implement pruning based on constraints
            continue
        path.append(c)
        backtrack(path, choices, results)
        path.pop()  # undo change so siblings start with correct state

• Ensure you append a copy of path when recording results.
• Implement should_prune to check feasibility early (bounds, duplicates, constraints).

4-week mentoring plan (goal: mastery of recursion/backtracking)

Week 1 — Foundations

• Read: "Recursion" chapter from CLRS or online tutorials; blog post on backtracking patterns.
• Exercises: simple recursion (factorial, Fibonacci), depth-first traversal.
• Pair: 2x 1-hour sessions to review mental model and pointer/aliasing issues.

Week 2 — Backtracking patterns

• Read: Articles on path-copy vs in-place backtracking, pruning heuristics.
• Exercises: Permutations, combinations, subsequence generation; test cases that reveal shared-mutable bugs.
• Pair: Implement permutations together, emphasize append(copy)/pop.

Week 3 — Pruning & optimization

• Read: Constraint propagation, branch-and-bound overview.
• Exercises: N-Queens with column/diagonal pruning; Sudoku solver with simple heuristics.
• Pair: Profile a slow backtracking solution, add pruning, compare performance.

Week 4 — Production readiness & review

• Exercises: Convert a working backtracking solver into library-quality code: docstrings, unit tests, edge cases, complexity notes.
• Pair: Code-review simulation where mentee reviews and fixes similar mistakes.
• Outcome: Final 1:1 retrospective, checklist for future PRs (mutability, copies, pruning, test coverage).

Measurement: weekly deliverables, passing unit tests, performance improvement (time/memory) on benchmarks, and independent PR demonstrating applied fixes.

1. Sort + early-break

• What: Sort candidate numbers ascending before recursion. In each recursion, when iterating remaining candidates, stop the loop as soon as candidate > (remaining target).
• How it prunes: Any later numbers (≥ current) will also exceed the target, so you eliminate all those branches in one check instead of exploring them.
• Overhead: O(n log n) one-time sort; negligible per-node cost (a comparison and a break). Best when many larger candidates exist.

2. Bound checks (prefix sums / lower bounds)

• What: Precompute prefix sums or maintain running min/max possible sums for remaining items. At a node, check if remaining target is achievable: e.g., remaining_target < min_possible_sum or > max_possible_sum.
• How it prunes: Cuts whole subtrees that cannot meet the target because even taking all smallest or largest remaining elements cannot reach it.
• Overhead: O(n) precomputation for prefix sums or O(1) incremental updates per recursion; extra memory O(n) for prefix arrays. Slight computation per node but saves large unexplorable subtrees.

3. Skip duplicates / frequency pruning

• What: Collapse duplicates into (value, count) pairs or, when iterating, skip choosing the same value at the same recursion level (classic dedup pattern).
• How it prunes: Avoids exploring symmetric branches that differ only by ordering or repeated selection order — reduces factorial/combinatorial blow-up from permutations of identical elements.
• Overhead: Small bookkeeping: frequency map construction O(n) or checks to skip equal neighbors after sorting. Slightly more complex recursion logic to iterate allowed counts (0..freq) rather than binary include/exclude.

Trade-offs summary:

• Combine techniques for multiplicative savings: sorting enables early-break and makes duplicate skipping easy. Bound checks add constant-time node pruning but require precomputation/maintenance. Frequency collapsing reduces branching factor at the cost of more complex recursion state. Choose based on input characteristics (duplicates present, candidate magnitude distribution).

Forward checking, AC-3, MAC and MRV are complementary techniques that reduce search in backtracking CSP solvers by pruning inconsistent values early. Below I describe each: algorithmic steps, how domains get pruned, and how to integrate into a recursive backtracker (illustrated with Sudoku / graph coloring).

Forward Checking

• Steps: when you assign variable X = v, for every unassigned neighbor Y (sharing a constraint), remove values from Y’s domain that conflict with v. If any domain becomes empty, backtrack.
• Pruning: only removes values directly inconsistent with the most recent assignment (one-step lookahead).
• Integration: in backtrack(assignments):
  1. choose variable (possibly MRV)
  2. for each value in domain:
     • push a copy/list of pruned (for restoration)
     • perform forward check and prune neighbor domains
     • recurse if no domain emptied
     • undo prunes on return
• Example: Sudoku — assign a digit to a cell; remove that digit from peers’ domains.

Arc Consistency (AC-3)

• Steps: Maintain a queue of arcs (Xi, Xj). For an arc (Xi,Xj), revise Xi: remove values in Xi’s domain that have no compatible value in Xj’s domain. If Xi’s domain shrinks, enqueue all arcs (Xk,Xi) for neighbors Xk.
• Pruning: enforces consistency across arcs until fixed point; can remove values that forward checking misses because it propagates beyond immediate neighbors.
• Integration: apply AC-3 as preprocessing to reduce domains; also can be invoked after each assignment (but running full AC-3 every time can be costlier).

Maintaining Arc Consistency (MAC)

• Steps: MAC applies AC-3 (or similar AC algorithm) incrementally after each assignment, using current domains and only relevant arcs.
• Pruning: strongest among these — enforces global arc consistency after each assignment, often dramatically reducing future branching.
• Integration: in backtrack, after choosing value for X, run MAC (AC-3 limited to arcs affected). If any domain becomes empty, backtrack. Restore domains on backtrack (record pruned values).

Minimum Remaining Values (MRV) heuristic

• Steps: select next variable with smallest domain (fewest legal values). Break ties with degree heuristic (most constraints).
• Pruning: MRV itself doesn’t prune domains but drastically reduces branching factor and exposes failures earlier, improving the effectiveness of forward checking / MAC.
• Integration: use MRV to pick variable at each recursion level.

Putting it together (workflow)

1. Preprocess: run AC-3 once to trim domains.
2. In backtrack:
   • pick var with MRV
   • for each value (optionally order by least-constraining-value):
     • assign, record prunes
     • run forward checking or MAC (prefer MAC when cost justified)
     • recurse
     • undo prunes and unassign

Trade-offs

• Forward checking is cheap per assignment but weaker.
• AC-3 as preprocessing is cheap and helpful; full MAC is strongest but more CPU per node.
• MRV multiplies benefits by failing early.

Practical tip: For Sudoku, AC-3 + MRV + least-constraining-value with backtracking solves puzzles quickly. For graph coloring, MAC+MRV is effective when colors/domains are small.

Approach: convert recursive DFS into an explicit-stack iterative backtracker. Maintain bitmasks for rows/cols/boxes (9 bits). Use MRV: at each step pick the empty cell with fewest candidates. Stack frames store cell index, candidate bitmask, and next candidate to try. On push we assign a digit, update masks and mark cell filled; on pop (backtrack) we undo masks and clear cell.

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

bool solveSudokuIterative(vector<vector<int>>& board) {
    const int N = 9;
    array<int,9> row{}, col{}, box{};
    vector<int> empties;
    auto boxId = [&](int r,int c){ return (r/3)*3 + (c/3); };
    // init masks (1 means available)
    for(int r=0;r<N;++r) for(int c=0;c<N;++c){
        int v = board[r][c];
        if(v==0) empties.push_back(r*9+c);
        else {
            int bit = 1 << (v-1);
            row[r] &= ~0; col[c] &= ~0; box[boxId(r,c)] &= ~0; // placeholder
        }
    }
    // set full-ones then clear used bits
    for(int i=0;i<9;i++){ row[i]=col[i]=box[i]=(1<<9)-1; }
    for(int r=0;r<N;++r) for(int c=0;c<N;++c){
        int v=board[r][c];
        if(v){
            int m = ~(1<<(v-1));
            row[r] &= m; col[c] &= m; box[boxId(r,c)] &= m;
        }
    }
    if(empties.empty()) return true;
    // stack frame: index into empties, candidates mask, tried mask
    struct Frame { int idx; int cand; int tried; };
    vector<Frame> stack;
    // helper to compute MRV index among remaining empties not yet assigned
    auto computeMRV = [&](const vector<int>& remaining)->pair<int,int>{
        int bestPos=-1, bestCount=10;
        int bestMask=0;
        for(int i=0;i<(int)remaining.size();++i){
            int rc = remaining[i];
            int r=rc/9,c=rc%9;
            int mask = row[r] & col[c] & box[boxId(r,c)];
            int cnt = __builtin_popcount(mask);
            if(cnt==0) return {-1,0};
            if(cnt < bestCount){ bestCount=cnt; bestPos=i; bestMask=mask; if(cnt==1) break; }
        }
        return {bestPos,bestMask};
    };
    vector<int> rem = empties;
    while(true){
        if(rem.empty()) return true;
        // MRV select
        auto [pos, mask] = computeMRV(rem);
        if(pos==-1){
            // backtrack
            if(stack.empty()) return false;
            auto f = stack.back(); stack.pop_back();
            int rc = rem.size()? rem.back() : -1; // not used
            int r = f.idx/9, c = f.idx%9, b=boxId(r,c);
            // undo previous assignment stored in tried as last tried digit
            int lastTried = f.tried;
            int digit = __builtin_ctz(lastTried)+1;
            board[r][c]=0;
            row[r] |= (1<<(digit-1));
            col[c] |= (1<<(digit-1));
            box[b] |= (1<<(digit-1));
            // rebuild rem: put this cell back front
            rem.push_back(f.idx);
            // remove that tried bit from candidate set and allow trying next on re-push
            f.cand &= ~lastTried;
            if(f.cand) {
                // try next candidate immediately
                int pick = f.cand & -f.cand;
                f.tried = pick;
                stack.push_back(f);
                int d = __builtin_ctz(pick)+1;
                board[r][c]=d;
                row[r] &= ~pick; col[c] &= ~pick; box[b] &= ~pick;
                rem.pop_back(); // filled
            }
            continue;
        }
        int rc = rem[pos];
        int r=rc/9,c=rc%9,b=boxId(r,c);
        int pick = mask & -mask; // choose lowest candidate (could choose other ordering)
        // prepare frame
        Frame fr{rc, mask, pick};
        // assign
        int d = __builtin_ctz(pick)+1;
        board[r][c]=d;
        row[r] &= ~pick; col[c] &= ~pick; box[b] &= ~pick;
        // push frame and remove from rem
        stack.push_back(fr);
        rem.erase(rem.begin()+pos);
    }
    return false;
}

Key points:

• Frame stores cell index (rc), current candidate mask, and the last tried bit (so on backtrack we know which digit to undo and what remains).
• Push when assigning a digit; pop when no candidates remain or a deeper failure forces backtracking.
• MRV selects the empty cell with fewest candidates by intersecting row/col/box masks; computing __builtin_popcount gives the count.
  Complexity: same search tree as recursive backtracking; masks give O(1) candidate checks. Edge cases: ensure mask zero handled (dead end), maintain consistent undo of masks.

Approach: use an explicit stack that stores a node plus a visited flag. We push nodes as we traverse down; when we pop a node:

• if not visited, push it back marked visited, then push its right and left children (not visited). This ensures left and right are processed before the visited node is popped the second time — yielding postorder (left, right, root). This keeps stack height proportional to tree height h (in worst case skewed tree h = n).

import java.util.*;
public class Solution {
    public static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int v){ val = v; }
    }

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;

        // stack of pairs: node + visited flag
        Deque<Pair> stack = new ArrayDeque<>();
        stack.push(new Pair(root, false));

        while (!stack.isEmpty()) {
            Pair p = stack.pop();
            TreeNode node = p.node;
            if (node == null) continue;
            if (p.visited) {
                // second time we see it -> add to result
                res.add(node.val);
            } else {
                // push node as visited, then push right and left (not visited)
                stack.push(new Pair(node, true));
                if (node.right != null) stack.push(new Pair(node.right, false));
                if (node.left  != null) stack.push(new Pair(node.left, false));
            }
        }
        return res;
    }

    // simple pair class
    private static class Pair {
        TreeNode node;
        boolean visited;
        Pair(TreeNode n, boolean v){ node = n; visited = v; }
    }
}

Key points:

• Correctness: node is added only after left and right have been pushed and processed because we re-push node with visited=true before children.
• Time: O(n) — each node is pushed/popped a constant number of times.
• Space: O(h) — stack holds nodes along a root-to-leaf path plus a few siblings; worst-case skewed tree h = n.
  Edge cases:
• null root -> empty list
• skewed left/right tree -> stack depth equals tree height (O(n)), which matches O(h) bound
• duplicate values or single-node tree handled naturally

Alternative: single-stack with prev pointer or reverse-preorder (root,right,left then reverse result). The visited-flag approach is explicit and easy to reason about.