Exercises — Backtracking problems — N-Queens, Sudoku solver, all permutations - subsets

Each element is a yes/no coin flip: in the subset or out. Four independent flips ⇒ $2\times 2\times 2\times 2=2^4=\boxed{16}$. The formula is $2^n$ where $n$ is the count of elements — the same $2^n$ the parent note derived.

Fill 5 slots left to right. First slot: 5 choices. Second: 4 remaining. Then 3, 2, 1. $5\times 4\times 3\times 2\times 1=5!=\boxed{120}$.

Compute each key. For $(2,5)$: $r-c=2-5=-3$. For $(4,7)$: $r-c=4-7=-3$. Equal ⇒ both land in the same diag (↘) bucket. (Check the others fail: columns $5\ne 7$; anti-diagonals $2+5=7$ vs $4+7=11$ differ.) So the ==diag set== catches it. See the diagonal picture below.

The code recurses skip before take, so the first leaf reached is "skip everything".

• bt(0) → skip 1 → bt(1) → skip 2 → bt(2): record []
• back at bt(1): take 2 → bt(2): record [2]
• back at bt(0): take 1 → bt(1) → skip 2 → record [1]
• take 2 → record [1,2]

Order: $\boxed{[],[2],[1],[1,2]}$. Exactly the parent's answer.

The loop always grabs the lowest available index first, so it dives 1 → 2 → 3.

• First leaf: pick 1, pick 2, pick 3 → record $[1,2,3]$.
• Pop back to after "1,2"; no index left ⇒ pop 2. Now pick 3, then only 2 remains → record $[1,3,2]$.

First two: $\boxed{[1,2,3],[1,3,2]}$.

$r//3=7//3=2$ (box-row, since rows 6–8 form the bottom band). $c//3=2//3=0$ (box-col, columns 0–2 are the left band). Flatten the $3\times 3$ grid of boxes: $2\times 3+0=\boxed{6}$ — the bottom-left box.

path is one single list object mutated in place (append/pop). res.append(path) stores four references to that same object. When the recursion fully unwinds, every push has a matching pop, so path ends empty. Result: res = [ [], [], [], [] ] — four aliases of the now-empty list. $\boxed{\text{4 empty lists}}$. The fix path[:] snapshots the current contents into a fresh list.

Queen at $(0,0)$ occupies: cols = {0}, diag = {0-0=0}, anti = {0+0=0}. Test each column c in row 1 (r=1):

• $c=0$: 0 in cols → pruned.
• $c=1$: r-c = 0, 0 in diag → pruned (↘ diagonal).
• $c=2$: cols? no. r-c = -1 no. r+c = 3 no → survives.
• $c=3$: cols? no. r-c = -2 no. r+c = 4 no → survives.

Pruned: $\{0,1\}$. Survivors: $\boxed{\{2,3\}}$ (2 columns). This is the pruning power — 2 of 4 branches die instantly.

There are $n!$ leaves. At each leaf we copy a list of length $n$ into res, costing $O(n)$. So total $\boxed{O(n\cdot n!)}$. Two factors: $n!$ = number of complete orderings (leaves of the tree); $n$ = cost per snapshot. The internal branching work is dominated by the leaf copies. (See Time-Complexity-of-Recursive-Algorithms for how leaf-count times per-leaf-cost gives the total.)

Sort first so equal elements are adjacent: [1,2,2]. Use the index-loop skeleton (choose a start, branch on each next element), and add the rule: within the same loop level, skip an element equal to the previous one.

def subsetsWithDup(nums):
    nums.sort(); res, path = [], []
    def bt(start):
        res.append(path[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i-1]:
                continue                      # skip duplicate sibling
            path.append(nums[i])
            bt(i+1)
            path.pop()
    bt(0); return res

Why i > start? The first copy of a value at each level is allowed (it starts a new branch); later equal siblings would re-generate an identical subtree, so we skip them. Distinct subsets: $\boxed{[],[1],[1,2],[1,2,2],[2],[2,2]}$ — 6 of them (not 8).

Backtrack over a running remain = target - sum. To avoid re-ordering the same multiset, pass a start index and never look left of it.

def combSum(cands, target):
    res, path = [], []
    def bt(start, remain):
        if remain == 0: res.append(path[:]); return
        if remain < 0: return                 # prune overshoot
        for i in range(start, len(cands)):
            path.append(cands[i])
            bt(i, remain - cands[i])          # i (not i+1): reuse allowed
            path.pop()
    bt(0, target); return res

Why bt(i, ...) not bt(i+1, ...)? Passing i again permits reusing the same candidate; passing start=i still blocks smaller-index numbers, killing reordered duplicates. Combinations summing to 8: $\boxed{[2,2,2,2],[3,5]}$. Check: $2+2+2+2=8$; $3+5=8$. (No third: $2+3+3=8$? yes! — wait, recount below.)

Careful recount of all multisets of $\{2,3,5\}$ summing to 8:

• all 2s: $2\cdot 4=8$ ✓ → [2,2,2,2]
• $2+3+3=8$ ✓ → [2,3,3]
• $3+5=8$ ✓ → [3,5]

So the true answer is $\boxed{[2,2,2,2],[2,3,3],[3,5]}$ — 3 combinations. (The remain < 0 prune stops paths like $2+5+\dots$ that overshoot.)

$N=4$: only two valid full placements exist (they are mirror images). Columns per row: $(1,3,0,2)$ and $(2,0,3,1)$. Count $=\boxed{2}$. $N=5$: the classic count is $\boxed{10}$ distinct solutions. (For reference the sequence of solution counts for $N=1,2,3,4,5,6$ is $1,0,0,2,10,4$ — note $N=2,3$ are impossible, a degenerate case the solver handles by simply recording nothing.)

Use Minimum Remaining Values (MRV): among all empty cells, always fill the one with the fewest legal candidate digits first. Why it helps: a cell with only 1 or 2 options has a low branching factor, so recursing there splits the tree into few subtrees. Filling a low-freedom cell early fails fast on dead branches instead of after deep detours. This is a form of Branch-and-Bound / CSP variable ordering — it never removes a valid solution (we still try every candidate of the chosen cell), it only reorders which cell we commit to, so correctness is preserved while the average tree shrinks dramatically. A cell with 0 candidates is an immediate dead end — MRV detects it soonest, the ultimate early prune.

Overlapping subproblems — e.g. counting paths in a grid, or Fibonacci-like recurrences. Backtracking re-explores the same partial state through different choice orders, redoing identical work exponentially. The winner is Dynamic-Programming: it memoizes each distinct subproblem once, turning exponential re-exploration into polynomial table lookups. Backtracking shines when subproblems are distinct (each partial board is unique); DP shines when they repeat.

Why must every choose have a matching un-choose? ::: Because the state (path, board, used) is shared and mutated; without restoring it, sibling branches inherit stale choices and emit garbage.