Recursion and Backtracking Questions

To generate the power set recursively, we can build subsets by deciding for each element whether to include it (choose) or not (skip). The recursion processes one element at a time and appends both branches.

def power_set(nums):
    """
    Returns list of subsets (each subset is a list).
    nums: list of unique integers
    """
    result = []
    
    def helper(i, current):
        # base: processed all elements
        if i == len(nums):
            result.append(current.copy())
            return
        # exclude nums[i]
        helper(i + 1, current)
        # include nums[i]
        current.append(nums[i])
        helper(i + 1, current)
        current.pop()  # backtrack

    helper(0, [])
    return result

# Example
print(power_set([1,2,3]))
# Output (order may vary): [[], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]]

Key points:

• Time complexity: O(2^n * n) — there are 2^n subsets and copying/current-building costs up to O(n) across generation.
• Space complexity: O(2^n * n) for storing all subsets plus O(n) recursion stack.

ML preprocessing considerations for large n (up to 30):

• 2^30 ≈ 1e9 subsets — infeasible to generate or store. Instead:
  • Avoid full power set; sample subsets randomly or generate only subsets up to a small k (combinations) if domain permits.
  • Use feature selection/embedding to reduce dimensionality before subset enumeration.
  • If enumeration is required for combinatorial search, use streaming generators (yield) and strict memory limits, or distributed/online algorithms and pruning (e.g., beam search, heuristic search).
  • Parallelize generation and use disk-backed stores or probabilistic data structures (Bloom filters) if approximate membership suffices.

Technique overview:
Use canonicalization to map each state’s symmetry-equivalent group to a single representative, then store/lookup only that representative during recursive search. This prunes branches that are isomorphic under symmetry (rotations, reflections, relabelings).

How to build canonical form (example: NxN puzzle with board rotations/reflections):

1. Enumerate group G of symmetries (for square board: 8 transforms: 4 rotations × 2 reflections).
2. For a given state S, generate S' = {g(S) | g ∈ G}.
3. Define canonical(S) = min(S') under a deterministic total order (lexicographic flattening or packed integer).
4. Use canonical(S) as the key in visited set / transposition table.

Implementation notes:

• Represent board compactly (bitboard, bytes) so transforms and comparisons are fast.
• Precompute transform mappings (index permutations) to apply symmetries by reindexing rather than copying.
• Store canonical only: when exploring child, compute canonical(child); if seen, skip; else insert and recurse.

Hashing/isomorphism:

• Hash canonical(S) (e.g., 64-bit Murmur or Zobrist-like random hashing) to store in hash table. For collision safety, store short fingerprint + small canonical data or verify on collision.

Memory overhead vs pruning benefit:

• Overhead: computing canonical adds CPU cost (~|G| transforms × transform cost) and storing canonical keys increases memory by key size per visited node. If canonicalizing to same-size key, overhead is O(visited_count * key_size).
• Benefit: reduces search tree by factor approx |G_relevant| when many states are symmetric; pruning can convert exponential blow-up into manageable sizes. Empirically for puzzles with full symmetry (e.g., 8 symmetries) you often see up to ~8× fewer unique states; cost amortizes when branching factor × depth is large.
• Trade-offs: For small/deep searches or cheap state generation, CPU cost of canonicalization may outweigh benefit. For memory-constrained settings, prefer partial canonicalization (e.g., handle rotations only) or use probabilistic hashes (lower memory: store 64-bit fingerprints) with rare false positives accepted.

When to use:

• Use when symmetries are frequent and cheap to enumerate, state representation is compact, and search explores many symmetric equivalents (e.g., game tree search, combinatorial puzzle solving).

A standard recursive/backtracking approach explores include/exclude for each element. At each recursion we either include nums[i] in the current partial subset or not; we append a copy of the partial subset to results to avoid shared mutable-state bugs.

from typing import List

def powerset(nums: List[int]) -> List[List[int]]:
    """
    Return all subsets of nums (unique integers).
    Uses recursion/backtracking. Order of subsets doesn't matter.
    """
    results: List[List[int]] = []

    def backtrack(index: int, partial: List[int]):
        # record a snapshot/copy of current partial subset
        results.append(partial.copy())

        # explore further choices
        for i in range(index, len(nums)):
            # include nums[i]
            partial.append(nums[i])
            backtrack(i + 1, partial)
            # remove last to backtrack; partial is mutated but snapshots were copied into results
            partial.pop()

    backtrack(0, [])
    return results

Key points:

• We append partial.copy() (not partial) to results so later mutations don't affect stored subsets — this prevents shared mutable-state bugs.
• The recursion iterates choices starting from current index to avoid duplicates and ensure each combination appears once.

Time complexity: O(n * 2^n) — 2^n subsets and copying each subset costs up to O(n).
Space complexity: O(n * 2^n) for output plus O(n) recursion depth auxiliary space.

Edge cases:

• nums = [] returns [[]].
• nums with single element returns [[], [x]].
• Since input elements are unique, no extra deduplication needed.

Approach: treat Sudoku as a CSP. Maintain domains (candidates) for each empty cell, use Minimum Remaining Values (MRV) to pick next cell, apply forward-checking (prune domains after assignment) and backtrack when a domain becomes empty.

def solve_sudoku(board):
    """
    board: 9x9 list of lists, 0 means empty.
    Returns True and fills board in-place if solvable, else False.
    """
    # Precompute peers and initial domains
    rows = cols = range(9)
    def box_index(r,c): return (r//3)*3 + (c//3)
    peers = {}
    for r in rows:
        for c in cols:
            p = set()
            p |= {(r, j) for j in cols if j!=c}
            p |= {(i, c) for i in rows if i!=r}
            p |= {(i,j) for i in range((r//3)*3,(r//3)*3+3)
                      for j in range((c//3)*3,(c//3)*3+3)
                      if (i,j)!=(r,c)}
            peers[(r,c)] = p

    # domains init
    domains = {}
    for r in rows:
        for c in cols:
            if board[r][c]:
                domains[(r,c)] = {board[r][c]}
            else:
                used = {board[i][j] for (i,j) in peers[(r,c)] if board[i][j]}
                domains[(r,c)] = set(range(1,10)) - used

    def select_var():
        # MRV: choose unassigned cell with smallest domain >1
        unassigned = [(len(domains[pos]), pos) for pos in domains if board[pos[0]][pos[1]]==0]
        if not unassigned: return None
        return min(unassigned)[1]

    def forward_assign(pos, val, removed):
        board[pos[0]][pos[1]] = val
        domains[pos] = {val}
        # remove val from peers' domains; record removals for backtrack
        for p in peers[pos]:
            if val in domains[p]:
                domains[p].remove(val)
                removed.setdefault(p, set()).add(val)

    def undo_assign(pos, removed, prev_domain):
        board[pos[0]][pos[1]] = 0
        domains[pos] = prev_domain
        for p,vals in removed.items():
            domains[p] |= vals

    def backtrack():
        var = select_var()
        if var is None:
            return True
        domain_snapshot = domains[var].copy()
        # try values in domain (could order by least-constraining-value)
        for val in sorted(domain_snapshot):
            # copy minimal change logs
            removed = {}
            prev_domain = domains[var].copy()
            forward_assign(var, val, removed)
            # fail-fast: if any peer's domain empty -> undo
            if all(domains[p] for p in peers[var]):
                if backtrack():
                    return True
            undo_assign(var, removed, prev_domain)
        return False

    # early failure
    if any(len(domains[p])==0 for p in domains): return False
    return backtrack()

Key points:

• Candidate generation: initial domain = {1..9} minus numbers seen in row/col/box.
• Heuristic: MRV picks the most constrained cell; tie-break with degree or least-constraining-value.
• Pruning: forward-checking removes assigned value from peers; detect empty domain to prune early. Stronger propagation (AC-3 / full arc-consistency) can be added.

Time/space trade-offs:

• Naive backtracking (no domains) uses less memory but explores many futile branches -> exponential time.
• Maintaining domains + forward-checking increases memory (domains per cell, logs for undo) and CPU per assignment but prunes massively, reducing search tree size; typical practical speed-up is orders of magnitude.
• Full constraint propagation (arc-consistency) further reduces branching but costs more upfront and per-step CPU; best when puzzles are hard or many constraints interact.
  Edge cases: unsolvable board, multiple solutions (solver returns first), invalid initial board (detect conflicting fixed values).

Recursion: a function calls itself with simpler inputs until a base case stops further calls. Two parts:

• Base case: simplest input with a direct answer (no further recursion).
• Recursive case: reduces the problem and calls the function again.

Call stack and frames:

• Each call creates a stack frame containing the function’s parameters, local variables, and return address.
• Frames are pushed on call, popped on return; local variables live only in their frame.
• Return values propagate back to the caller via the stack: the callee computes a value, returns it, then the caller resumes and uses it.

Example (Python):

def factorial(n):
    if n == 0:            # base case
        return 1
    return n * factorial(n - 1)  # recursive case

factorial(4)

Call-return sequence (top = most recent frame):

1. Push frame: factorial(4)
   • n=4, waiting for factorial(3)
2. Push: factorial(3)
   • n=3, waiting for factorial(2)
3. Push: factorial(2)
   • n=2, waiting for factorial(1)
4. Push: factorial(1)
   • n=1, waiting for factorial(0)
5. Push: factorial(0)
   • n=0 -> base case: return 1; pop frame
6. Resume factorial(1): receive 1 -> compute 1 * 1 = 1; return 1; pop
7. Resume factorial(2): receive 1 -> compute 2 * 1 = 2; return 2; pop
8. Resume factorial(3): receive 2 -> compute 3 * 2 = 6; return 6; pop
9. Resume factorial(4): receive 6 -> compute 4 * 6 = 24; return 24; pop (stack empty)

Notes:

• Each frame’s local n is independent.
• Deep recursion can overflow the call stack; use iteration or tail recursion optimization where available. For ML engineers, be cautious with recursion in production code and prefer iterative or vectorized solutions for large inputs.