Backtracking

# python
# LC 216 - Combination Sum III
# IDEA: choose a digit, explore with the digits after it, un-choose; record at the leaf
# time = O(C(9,k) * k), space = O(k)   at most C(9,k) leaves, O(k) to copy each
def combinationSum3(k, n):
    res = []
    path = []

    def backtrack(start, remain):
        if len(path) == k:                 # end condition: a leaf of the decision tree
            if remain == 0:
                res.append(path[:])        # copy: path keeps changing after this line
            return
        for digit in range(start, 10):     # choice list: the digits not tried yet, in order
            if digit > remain:             # digits ascend, so every later one is too big
                break
            path.append(digit)             # 1) choose
            backtrack(digit + 1, remain - digit)   # 2) explore (digit + 1 -> each used once)
            path.pop()                     # 3) un-choose

    backtrack(1, n)
    return res

// java
// LC 216 - Combination Sum III
// IDEA: choose a digit, explore with the digits after it, un-choose; record at the leaf
// time = O(C(9,k) * k), space = O(k)
public List<List<Integer>> combinationSum3(int k, int n) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(1, n, k, new ArrayList<>(), res);
    return res;
}

private void backtrack(int start, int remain, int k, List<Integer> path, List<List<Integer>> res) {
    if (path.size() == k) {                     // end condition
        if (remain == 0) {
            res.add(new ArrayList<>(path));     // copy, not the live reference
        }
        return;
    }
    for (int digit = start; digit <= 9; digit++) {
        if (digit > remain) {                   // ascending digits: the rest are too big
            break;
        }
        path.add(digit);                        // 1) choose
        backtrack(digit + 1, remain - digit, k, path, res);   // 2) explore
        path.remove(path.size() - 1);           // 3) un-choose
    }
}

# python
# LC 39 - Combination Sum
# IDEA: pass i (not i + 1) so a candidate can be picked again; start_idx keeps each set in one order
# time = O(n^(T/M + 1)), space = O(T/M)   T = target, M = smallest candidate
def combinationSum(candidates, target):
    candidates.sort()                      # sorted, so the first too-big candidate ends the loop
    res = []
    path = []

    def backtrack(start, remain):
        if remain == 0:
            res.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remain:     # every candidate after i is bigger still
                break
            path.append(candidates[i])
            backtrack(i, remain - candidates[i])   # i: the same candidate stays available
            path.pop()

    backtrack(0, target)
    return res

// java
// LC 39 - Combination Sum
// IDEA: pass i (not i + 1) so a candidate can be picked again; start_idx keeps each set in one order
// time = O(n^(T/M + 1)), space = O(T/M)
public List<List<Integer>> combinationSum(int[] candidates, int target) {
    Arrays.sort(candidates);
    List<List<Integer>> res = new ArrayList<>();
    backtrack(candidates, 0, target, new ArrayList<>(), res);
    return res;
}

private void backtrack(int[] candidates, int start, int remain, List<Integer> path, List<List<Integer>> res) {
    if (remain == 0) {
        res.add(new ArrayList<>(path));
        return;
    }
    for (int i = start; i < candidates.length; i++) {
        if (candidates[i] > remain) {           // sorted: the rest are bigger
            break;
        }
        path.add(candidates[i]);
        backtrack(candidates, i, remain - candidates[i], path, res);   // i: reuse allowed
        path.remove(path.size() - 1);
    }
}

backtrack(0, 7)
├─ 2 → backtrack(0, 5)
│  ├─ 2 → backtrack(0, 3)
│  │  ├─ 2 → backtrack(0, 1)     2 > 1: break
│  │  ├─ 3 → backtrack(1, 0)     ✅ [2, 2, 3]
│  │  └─ 6 > 3: break
│  ├─ 3 → backtrack(1, 2)        3 > 2: break
│  └─ 6 > 5: break
├─ 3 → backtrack(1, 4)
│  ├─ 3 → backtrack(1, 1)        3 > 1: break
│  └─ 6 > 4: break
├─ 6 → backtrack(2, 1)           6 > 1: break
└─ 7 → backtrack(3, 0)           ✅ [7]

# python
# LC 78 - Subsets
# IDEA: record the path at EVERY node (pre-order); pass i + 1 so each element is used once
# time = O(2^n * n), space = O(n)   2^n subsets, O(n) to copy each
def subsets(nums):
    res = []
    path = []

    def backtrack(start):
        res.append(path[:])                # every node is an answer, the empty set included
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()

    backtrack(0)
    return res

// java
// LC 78 - Subsets
// IDEA: record the path at EVERY node (pre-order); pass i + 1 so each element is used once
// time = O(2^n * n), space = O(n)
public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(nums, 0, new ArrayList<>(), res);
    return res;
}

private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
    res.add(new ArrayList<>(path));             // every node is an answer
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        backtrack(nums, i + 1, path, res);      // i + 1: each element used once
        path.remove(path.size() - 1);
    }
}

# python
# LC 78 - Subsets (include / exclude)
# IDEA: at depth i decide nums[i]: take it, recurse, undo, then recurse without it; record at the leaf
# time = O(2^n * n), space = O(n)
def subsets(nums):
    res = []
    path = []

    def backtrack(i):
        if i == len(nums):               # every element decided: one subset
            res.append(path[:])
            return
        path.append(nums[i])             # include nums[i]
        backtrack(i + 1)
        path.pop()
        backtrack(i + 1)                 # exclude nums[i]

    backtrack(0)
    return res

nums = [1, 2, 3]       record on entry, then try i = start .. n-1
start=0  []          -> [1] -> start=1 [1]     -> [1,2] -> start=2 [1,2] -> [1,2,3]
                                               -> [1,3]
                     -> [2] -> start=2 [2]     -> [2,3]
                     -> [3]
res = [], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]

# python
# LC 90 - Subsets II
# IDEA: sort, then skip a value equal to the previous one at the SAME level (i > start)
# time = O(2^n * n), space = O(n)   the O(n log n) sort is dominated
def subsetsWithDup(nums):
    nums.sort()                            # duplicates become adjacent
    res = []
    path = []

    def backtrack(start):
        res.append(path[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:   # same level, same value: same subtree
                continue
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()

    backtrack(0)
    return res

// java
// LC 90 - Subsets II
// IDEA: sort, then skip a value equal to the previous one at the SAME level (i > start)
// time = O(2^n * n), space = O(n)
public List<List<Integer>> subsetsWithDup(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    backtrack(nums, 0, new ArrayList<>(), res);
    return res;
}

private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
    res.add(new ArrayList<>(path));
    for (int i = start; i < nums.length; i++) {
        if (i > start && nums[i] == nums[i - 1]) {   // same level, same value: skip
            continue;
        }
        path.add(nums[i]);
        backtrack(nums, i + 1, path, res);
        path.remove(path.size() - 1);
    }
}

# python
# LC 46 - Permutations
# IDEA: BACKTRACK with a `used` array: loop from 0 every level, skip what is already on the path
# time = O(n! * n), space = O(n)     n! permutations, O(n) to copy each
def permute(nums):
    res = []
    path = []
    used = [False] * len(nums)

    def backtrack():
        if len(path) == len(nums):
            res.append(path[:])            # copy the path
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True                 # choose
            path.append(nums[i])
            backtrack()                    # explore
            path.pop()                     # un-choose
            used[i] = False

    backtrack()
    return res

// java
// LC 46 - Permutations
// IDEA: BACKTRACK with a `used` array: loop from 0 every level, skip what is already on the path
// time = O(n! * n), space = O(n)
public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(nums, new boolean[nums.length], new ArrayList<>(), res);
    return res;
}

private void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
    if (path.size() == nums.length) {
        res.add(new ArrayList<>(path));
        return;
    }
    for (int i = 0; i < nums.length; i++) {     // no start index: order matters
        if (used[i]) {
            continue;
        }
        used[i] = true;                         // choose
        path.add(nums[i]);
        backtrack(nums, used, path, res);       // explore
        path.remove(path.size() - 1);           // un-choose
        used[i] = false;
    }
}

dfs([])                       used={}
├─ 1 → dfs([1])               used={1}
│  ├─ 2 → dfs([1,2]) → 3 → [1,2,3] ✅
│  └─ 3 → dfs([1,3]) → 2 → [1,3,2] ✅
├─ 2 → dfs([2])               used={2}
│  ├─ 1 → [2,1] → 3 → [2,1,3] ✅
│  └─ 3 → [2,3] → 1 → [2,3,1] ✅
└─ 3 → dfs([3])               used={3}
   ├─ 1 → [3,1] → 2 → [3,1,2] ✅
   └─ 2 → [3,2] → 1 → [3,2,1] ✅

# python
# LC 47 - Permutations II
# IDEA: BACKTRACK over a Counter of distinct values (decrement on choose, increment on un-choose)
# time = O(n! * n), space = O(n)     duplicates only prune, they do not change the bound
from collections import Counter

def permuteUnique(nums):
    res = []
    path = []
    count = Counter(nums)

    def backtrack():
        if len(path) == len(nums):
            res.append(path[:])
            return
        for value in count:                # each DISTINCT value once per level
            if count[value] == 0:
                continue
            path.append(value)
            count[value] -= 1
            backtrack()
            path.pop()                     # undo both: the path and the count
            count[value] += 1

    backtrack()
    return res

# python
# LC 77 - Combinations
# IDEA: start_idx + a size gate, and never start a branch that cannot still reach k numbers
# time = O(C(n,k) * k), space = O(k)   one copy per combination
def combine(n, k):
    res = []
    path = []

    def backtrack(start):
        if len(path) == k:
            res.append(path[:])            # path[:] and list(path) are both a copy
            return
        need = k - len(path)
        for i in range(start, n - need + 2):   # leave room for the need - 1 numbers after i
            path.append(i)
            backtrack(i + 1)
            path.pop()

    backtrack(1)
    return res

// java
// LC 77 - Combinations
// IDEA: start_idx + a size gate, and never start a branch that cannot still reach k numbers
// time = O(C(n,k) * k), space = O(k)
public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(1, n, k, new ArrayList<>(), res);
    return res;
}

private void backtrack(int start, int n, int k, List<Integer> path, List<List<Integer>> res) {
    if (path.size() == k) {
        res.add(new ArrayList<>(path));
        return;
    }
    int need = k - path.size();
    for (int i = start; i <= n - need + 1; i++) {   // leave room for the need - 1 numbers after i
        path.add(i);
        backtrack(i + 1, n, k, path, res);
        path.remove(path.size() - 1);
    }
}

# python
# LC 40 - Combination Sum II
# IDEA: sort; skip same-level duplicates; break once the sum overshoots; pass i + 1 (use once)
# time = O(2^n * n), space = O(n)    each candidate used at most once
def combinationSum2(candidates, target):
    candidates.sort()
    res = []
    path = []

    def backtrack(start, remain):
        if remain == 0:
            res.append(path[:])
            return
        for i in range(start, len(candidates)):
            if i > start and candidates[i] == candidates[i - 1]:   # same level, same value
                continue
            if candidates[i] > remain:     # sorted: everything after i overshoots too
                break
            path.append(candidates[i])
            backtrack(i + 1, remain - candidates[i])   # i + 1: each candidate once
            path.pop()

    backtrack(0, target)
    return res

// java
// LC 40 - Combination Sum II
// IDEA: sort; skip same-level duplicates; break once the sum overshoots; pass i + 1 (use once)
// time = O(2^n * n), space = O(n)
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    Arrays.sort(candidates);
    List<List<Integer>> res = new ArrayList<>();
    backtrack(candidates, 0, target, new ArrayList<>(), res);
    return res;
}

private void backtrack(int[] candidates, int start, int remain, List<Integer> path, List<List<Integer>> res) {
    if (remain == 0) {
        res.add(new ArrayList<>(path));
        return;
    }
    for (int i = start; i < candidates.length; i++) {
        if (i > start && candidates[i] == candidates[i - 1]) {   // skip duplicates
            continue;
        }
        if (candidates[i] > remain) {           // sorted: stop
            break;
        }
        path.add(candidates[i]);
        backtrack(candidates, i + 1, remain - candidates[i], path, res);
        path.remove(path.size() - 1);
    }
}

# python
# LC 131 - Palindrome Partitioning
# IDEA: choose WHERE TO CUT: try every prefix s[start..end] that is a palindrome, recurse from end + 1
# time = O(2^n * n), space = O(n)    2^(n-1) cut sets, O(n) per palindrome check + copy
def partition(s):
    n = len(s)
    res = []
    path = []

    def is_palindrome(lo, hi):
        while lo < hi:
            if s[lo] != s[hi]:
                return False
            lo += 1
            hi -= 1
        return True

    def backtrack(start):
        if start == n:                     # no string left: every piece passed the gate
            res.append(path[:])
            return
        for end in range(start, n):        # every prefix, including the whole rest
            if is_palindrome(start, end):
                path.append(s[start:end + 1])
                backtrack(end + 1)         # recurse on the REST, from end + 1
                path.pop()

    backtrack(0)
    return res

// java
// LC 131 - Palindrome Partitioning
// IDEA: choose WHERE TO CUT: try every prefix s[start..end] that is a palindrome, recurse from end + 1
// time = O(2^n * n), space = O(n)
public List<List<String>> partition(String s) {
    List<List<String>> res = new ArrayList<>();
    backtrack(s, 0, new ArrayList<>(), res);
    return res;
}

private void backtrack(String s, int start, List<String> path, List<List<String>> res) {
    if (start == s.length()) {
        res.add(new ArrayList<>(path));
        return;
    }
    for (int end = start; end < s.length(); end++) {
        if (isPalindrome(s, start, end)) {
            path.add(s.substring(start, end + 1));
            backtrack(s, end + 1, path, res);    // the rest starts after this piece
            path.remove(path.size() - 1);
        }
    }
}

private boolean isPalindrome(String s, int lo, int hi) {
    while (lo < hi) {
        if (s.charAt(lo) != s.charAt(hi)) {
            return false;
        }
        lo++;
        hi--;
    }
    return true;
}

s = "aab"        gaps:  a|a|b  ->  2 gaps  ->  2^2 = 4 candidate partitions

start=0  "a"   ok ─┬─ start=1  "a"   ok ── start=2  "b" ok ── start=3  ["a","a","b"]
                   └─ start=1  "ab"  no  (not a palindrome — branch dies here)
start=0  "aa"  ok ─── start=2  "b"   ok ─────────────────── start=3  ["aa","b"]
start=0  "aab" no  (not a palindrome)

# python
# LC 131 - Palindrome Partitioning (precomputed palindrome table)
# IDEA : BACKTRACK + DP gate. dp[i][j] is built bottom-up so dp[i+1][j-1] is already known.
# time = O(2^n * n), space = O(n^2)   the O(n^2) table replaces an O(n) check per cut
def partition(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):          # i descends so the inner span is ready
        for j in range(i, n):
            dp[i][j] = s[i] == s[j] and (j - i < 2 or dp[i + 1][j - 1])

    res, path = [], []

    def backtrack(start):
        if start == n:
            res.append(path[:])             # copy — `path` is one shared list here
            return
        for end in range(start, n):
            if dp[start][end]:              # O(1) gate
                path.append(s[start:end + 1])
                backtrack(end + 1)          # `end + 1`, not `start + 1`
                path.pop()

    backtrack(0)
    return res

# python
# LC 79 - Word Search
# IDEA: DFS + backtracking: mark the cell, try 4 directions, restore the cell, then return
# time = O(m * n * 4^L), space = O(L)   L = len(word); 4 directions, minus the one we came from
def exist(board, word):
    rows, cols = len(board), len(board[0])

    def dfs(r, c, idx):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False
        if board[r][c] != word[idx]:       # also rejects "#", a cell on the current path
            return False
        if idx == len(word) - 1:
            return True

        saved = board[r][c]
        board[r][c] = "#"                  # mark: on the current path
        found = (dfs(r + 1, c, idx + 1) or
                 dfs(r - 1, c, idx + 1) or
                 dfs(r, c + 1, idx + 1) or
                 dfs(r, c - 1, idx + 1))
        board[r][c] = saved                # restore BEFORE returning
        return found

    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False

// java
// LC 79 - Word Search
// IDEA: DFS + backtracking: mark the cell, try 4 directions, restore the cell, then return
// time = O(m * n * 4^L), space = O(L)
public boolean exist(char[][] board, String word) {
    for (int r = 0; r < board.length; r++) {
        for (int c = 0; c < board[0].length; c++) {
            if (dfs(board, word, r, c, 0)) {
                return true;
            }
        }
    }
    return false;
}

private boolean dfs(char[][] board, String word, int r, int c, int idx) {
    if (r < 0 || r >= board.length || c < 0 || c >= board[0].length) {
        return false;
    }
    if (board[r][c] != word.charAt(idx)) {
        return false;
    }
    if (idx == word.length() - 1) {
        return true;
    }
    char saved = board[r][c];
    board[r][c] = '#';                          // mark
    boolean found = dfs(board, word, r + 1, c, idx + 1)
            || dfs(board, word, r - 1, c, idx + 1)
            || dfs(board, word, r, c + 1, idx + 1)
            || dfs(board, word, r, c - 1, idx + 1);
    board[r][c] = saved;                        // restore before returning
    return found;
}

# python
# time = O(g * 3^g), space = O(g)   g = gold cells (<= 25); after the first step a path has <= 3 unvisited directions
# LC 1219 - Path with Maximum Gold
# IDEA : DFS + backtrack from every gold cell; -1 marks "on the CURRENT path"
# https://github.com/yennanliu/CS_basics/blob/master/leetcode_python/Backtracking/path-with-maximum-gold.py
class Solution(object):
    def getMaximumGold(self, grid):
        self.max_gold = 0
        for y in range(len(grid)):
            for x in range(len(grid[0])):
                if grid[y][x] > 0:
                    self.dfs_helper(grid, x, y, 0)
        return self.max_gold

    def dfs_helper(self, grid, x, y, cur_gold):
        if x < 0 or x >= len(grid[0]) or y < 0 or y >= len(grid):
            return
        if grid[y][x] <= 0:           # 0 = no gold, -1 = already on THIS path
            return

        cur_gold += grid[y][x]        # int: this frame's own copy, never undone
        self.max_gold = max(self.max_gold, cur_gold)

        cache = grid[y][x]
        grid[y][x] = -1               # ---- mark: from here ...
        self.dfs_helper(grid, x + 1, y, cur_gold)   # every one of these four calls,
        self.dfs_helper(grid, x - 1, y, cur_gold)   # and every call THEY make,
        self.dfs_helper(grid, x, y + 1, cur_gold)   # sees (y, x) as -1
        self.dfs_helper(grid, x, y - 1, cur_gold)
        grid[y][x] = cache            # ---- ... to here: undo after the LAST branch returns

 1 enter (0,0) mark  -> [-1,  2] [ 3,  4]  cur=1
 2   enter (0,1) mark  -> [-1, -1] [ 3,  4]  cur=3        (0,0) still -1
 3     enter (1,1) mark  -> [-1, -1] [ 3, -1]  cur=7
 4       enter (1,0) mark  -> [-1, -1] [-1, -1]  cur=10   whole path 1->2->4->3 marked
 5       leave (1,0) undo  -> [-1, -1] [ 3, -1]
 6     leave (1,1) undo  -> [-1, -1] [ 3,  4]
 7   leave (0,1) undo  -> [-1,  2] [ 3,  4]               (0,1) free again, (0,0) is NOT
 8   enter (1,0) mark  -> [-1,  2] [-1,  4]  cur=4        (0,0)'s next direction: down
 9     enter (1,1) mark  -> [-1,  2] [-1, -1]  cur=8
10       enter (0,1) mark  -> [-1, -1] [-1, -1]  cur=10   (0,1) collected AGAIN, on a new path
11       leave (0,1) undo  -> [-1,  2] [-1, -1]
12     leave (1,1) undo  -> [-1,  2] [-1,  4]
13   leave (1,0) undo  -> [-1,  2] [ 3,  4]
14 leave (0,0) undo  -> [ 1,  2] [ 3,  4]               grid exactly as it started

# python
# LC 51 - N-Queens
# IDEA: one row per depth; cols / diag1 (row - col) / diag2 (row + col) sets make the attack test O(1)
# time = O(n!), space = O(n^2)       n choices, then at most n-1, ...; the board is n^2
def solveNQueens(n):
    result = []
    board = [["."] * n for _ in range(n)]
    cols = set()
    diag1 = set()   # row - col: top-left to bottom-right
    diag2 = set()   # row + col: top-right to bottom-left

    def backtrack(row):
        if row == n:
            result.append(["".join(r) for r in board])
            return
        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)
            board[row][col] = "Q"
            backtrack(row + 1)
            board[row][col] = "."          # undo all four pieces of state
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)

    backtrack(0)
    return result

// java
// LC 51 - N-Queens
// IDEA: one row per depth; boolean arrays for columns and both diagonals make the attack test O(1)
// time = O(n!), space = O(n^2)
public List<List<String>> solveNQueens(int n) {
    List<List<String>> result = new ArrayList<>();
    char[][] board = new char[n][n];
    for (char[] row : board) {
        Arrays.fill(row, '.');
    }
    // diag1 is indexed by row - col + n - 1 so it is never negative
    place(0, n, board, new boolean[n], new boolean[2 * n - 1], new boolean[2 * n - 1], result);
    return result;
}

private void place(int row, int n, char[][] board, boolean[] cols, boolean[] diag1,
                   boolean[] diag2, List<List<String>> result) {
    if (row == n) {
        List<String> rows = new ArrayList<>();
        for (char[] r : board) {
            rows.add(new String(r));
        }
        result.add(rows);
        return;
    }
    for (int col = 0; col < n; col++) {
        int d1 = row - col + n - 1;
        int d2 = row + col;
        if (cols[col] || diag1[d1] || diag2[d2]) {
            continue;
        }
        cols[col] = diag1[d1] = diag2[d2] = true;
        board[row][col] = 'Q';
        place(row + 1, n, board, cols, diag1, diag2, result);
        board[row][col] = '.';
        cols[col] = diag1[d1] = diag2[d2] = false;
    }
}

# python
# LC 37 - Sudoku Solver
# IDEA: one empty cell per depth; row / col / box sets make each digit test O(1); stop at the first fill
# time = O(9^m), space = O(m)        m = blank cells; the sets are a fixed 3 x 9
def solveSudoku(board):
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    empty = []
    for r in range(9):
        for c in range(9):
            if board[r][c] == ".":
                empty.append((r, c))
            else:
                digit = board[r][c]
                rows[r].add(digit)
                cols[c].add(digit)
                boxes[(r // 3) * 3 + c // 3].add(digit)

    def backtrack(idx):
        if idx == len(empty):
            return True                    # every blank filled: done
        r, c = empty[idx]
        box = (r // 3) * 3 + c // 3
        for digit in "123456789":
            if digit in rows[r] or digit in cols[c] or digit in boxes[box]:
                continue
            board[r][c] = digit
            rows[r].add(digit)
            cols[c].add(digit)
            boxes[box].add(digit)
            if backtrack(idx + 1):
                return True                # keep the board as it is
            board[r][c] = "."
            rows[r].remove(digit)
            cols[c].remove(digit)
            boxes[box].remove(digit)
        return False

    backtrack(0)

// java
// LC 37 - Sudoku Solver
// IDEA: one empty cell per depth; boolean tables for row / col / box; stop at the first fill
// time = O(9^m), space = O(m)
public void solveSudoku(char[][] board) {
    boolean[][] rows = new boolean[9][10];
    boolean[][] cols = new boolean[9][10];
    boolean[][] boxes = new boolean[9][10];
    List<int[]> empty = new ArrayList<>();
    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            if (board[r][c] == '.') {
                empty.add(new int[]{r, c});
            } else {
                int d = board[r][c] - '0';
                rows[r][d] = true;
                cols[c][d] = true;
                boxes[(r / 3) * 3 + c / 3][d] = true;
            }
        }
    }
    fill(0, board, empty, rows, cols, boxes);
}

private boolean fill(int idx, char[][] board, List<int[]> empty,
                     boolean[][] rows, boolean[][] cols, boolean[][] boxes) {
    if (idx == empty.size()) {
        return true;
    }
    int r = empty.get(idx)[0];
    int c = empty.get(idx)[1];
    int box = (r / 3) * 3 + c / 3;
    for (int d = 1; d <= 9; d++) {
        if (rows[r][d] || cols[c][d] || boxes[box][d]) {
            continue;
        }
        board[r][c] = (char) ('0' + d);
        rows[r][d] = cols[c][d] = boxes[box][d] = true;
        if (fill(idx + 1, board, empty, rows, cols, boxes)) {
            return true;
        }
        board[r][c] = '.';
        rows[r][d] = cols[c][d] = boxes[box][d] = false;
    }
    return false;
}

# python
# LC 526 - Beautiful Arrangement
# IDEA: fill position pos = 1..n; try only a value that passes the divisibility test AT THE CHOICE
# time = O(n!) worst case, far fewer after the prune, space = O(n)
def countArrangement(n):
    used = [False] * (n + 1)

    def backtrack(pos):
        if pos > n:
            return 1                       # every position filled with a legal value
        count = 0
        for value in range(1, n + 1):
            if used[value]:
                continue
            if value % pos != 0 and pos % value != 0:   # prune here, not at the leaf
                continue
            used[value] = True
            count += backtrack(pos + 1)
            used[value] = False
        return count

    return backtrack(1)

// java
// LC 526 - Beautiful Arrangement
// IDEA: fill position pos = 1..n; try only a value that passes the divisibility test AT THE CHOICE
// time = O(n!) worst case, far fewer after the prune, space = O(n)
public int countArrangement(int n) {
    return count(1, n, new boolean[n + 1]);
}

private int count(int pos, int n, boolean[] used) {
    if (pos > n) {
        return 1;
    }
    int total = 0;
    for (int value = 1; value <= n; value++) {
        if (used[value]) {
            continue;
        }
        if (value % pos != 0 && pos % value != 0) {   // prune at the choice
            continue;
        }
        used[value] = true;
        total += count(pos + 1, n, used);
        used[value] = false;
    }
    return total;
}

# python
# LC 698 - Partition to K Equal Sum Subsets
# IDEA: place each number (largest first) into a bucket; skip a bucket whose sum equals the previous one
# time = O(k^n) worst case, space = O(n)   memoising on a used-mask instead gives O(n * 2^n)
def canPartitionKSubsets(nums, k):
    total = sum(nums)
    if total % k != 0:
        return False
    target = total // k
    nums.sort(reverse=True)                # large numbers fail early
    if nums[0] > target:
        return False

    buckets = [0] * k

    def backtrack(index):
        if index == len(nums):
            return True                    # every number placed, no bucket over target
        for i in range(k):
            if buckets[i] + nums[index] > target:
                continue
            if i > 0 and buckets[i] == buckets[i - 1]:   # same sum: same subtree
                continue
            buckets[i] += nums[index]
            if backtrack(index + 1):
                return True                # return up the stack at once
            buckets[i] -= nums[index]
        return False

    return backtrack(0)

// java
// LC 698 - Partition to K Equal Sum Subsets
// IDEA: place each number (largest first) into a bucket; skip a bucket whose sum equals the previous one
// time = O(k^n) worst case, space = O(n)
public boolean canPartitionKSubsets(int[] nums, int k) {
    int total = 0;
    for (int x : nums) {
        total += x;
    }
    if (total % k != 0) {
        return false;
    }
    Arrays.sort(nums);                          // ascending: walk it from the end
    int target = total / k;
    if (nums[nums.length - 1] > target) {
        return false;
    }
    return place(nums, nums.length - 1, new int[k], target);
}

private boolean place(int[] nums, int index, int[] buckets, int target) {
    if (index < 0) {
        return true;
    }
    for (int i = 0; i < buckets.length; i++) {
        if (buckets[i] + nums[index] > target) {
            continue;
        }
        if (i > 0 && buckets[i] == buckets[i - 1]) {   // same sum: same subtree
            continue;
        }
        buckets[i] += nums[index];
        if (place(nums, index - 1, buckets, target)) {
            return true;                        // decision problem: stop at the first success
        }
        buckets[i] -= nums[index];
    }
    return false;
}

# python
# LC 113 - Path Sum II
# IDEA: carry cur_sum (int, never undone) and cache (list, popped after both children)
# time = O(n^2), space = O(n)        O(n) root-to-leaf paths, O(n) to copy each
class Solution(object):
    def pathSum(self, root, targetSum):
        self.res = []
        if not root:
            return self.res
        self.helper(root, targetSum, 0, [])
        return self.res

    def helper(self, root, targetSum, cur_sum, cache):
        if not root:
            return

        cur_sum += root.val        # int  -> rebinds LOCAL name to a NEW int (immutable)
        cache.append(root.val)     # list -> mutates the ONE shared list

        if not root.left and not root.right and cur_sum == targetSum:
            self.res.append(cache[:])   # snapshot, else later pops corrupt it

        self.helper(root.left,  targetSum, cur_sum, cache)
        self.helper(root.right, targetSum, cur_sum, cache)

        cache.pop()                # MUST backtrack the list ...
        # ... and NO `cur_sum -= root.val`: the int never changed for the parent

// java
// LC 113 - Path Sum II
// IDEA: curSum is an int (a copy per frame, never undone); path is one shared List (undone)
// time = O(n^2), space = O(n)
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
    List<List<Integer>> res = new ArrayList<>();
    helper(root, targetSum, 0, new ArrayList<>(), res);
    return res;
}

private void helper(TreeNode node, int targetSum, int curSum, List<Integer> path,
                    List<List<Integer>> res) {
    if (node == null) {
        return;
    }
    curSum += node.val;                         // int: this frame's own copy
    path.add(node.val);                         // List: the one shared object
    if (node.left == null && node.right == null && curSum == targetSum) {
        res.add(new ArrayList<>(path));
    }
    helper(node.left, targetSum, curSum, path, res);
    helper(node.right, targetSum, curSum, path, res);
    path.remove(path.size() - 1);               // undo the List, never the int
}

without pop                      with pop
visit 1: cache = [1]             visit 1: cache = [1]
visit 2: cache = [1,2]           visit 2: cache = [1,2]
return                           return -> pop() => [1]
visit 3: cache = [1,2,3]  wrong  visit 3: cache = [1,3]   correct

# python
if len(current) == target_length:   # fixed-size result (permutations, combinations of size k)
    result.append(current[:])
    return

if sum(current) == target:          # value-based result (subset sum, coin change)
    result.append(current[:])
    return

if index == len(input):             # exhausted input (string partition, IP addresses)
    if is_valid(current):
        result.append(result_repr)
    return