🎯 Top 25 PHP Recursion & Backtracking Interview Questions

Parent: Recursion & Backtracking Index

---

Quick Reference

---

Q1. Factorial [E]

Problem: Compute n! recursively.

---

🧠 How to Approach This

Step 1 — Recognize the pattern: n! = n × (n-1)! → linear recursion.

Step 2 — Base case: 0! = 1, 1! = 1

Step 3 — Algorithm:

1. If n <= 1, return 1

2. Return n * factorial(n-1)

function factorial(int $n): int
{
    if ($n <= 1) return 1;
    return $n * factorial($n - 1);
}

echo factorial(5);  // 120
echo factorial(10); // 3628800

Time: O(n) | Space: O(n)

---

Q2. Fibonacci (Memoized) [E]

Problem: Return nth Fibonacci number efficiently.

---

🧠 How to Approach This

Step 1 — Recognize the pattern: fib(n) = fib(n-1) + fib(n-2) → overlapping sub-problems → memoize.

Step 2 — Naive O(2ⁿ) is too slow. Cache computed values → O(n).

Step 3 — Algorithm:

1. Base: n <= 1 → return n

2. If cached, return cache[n]

3. cache[n] = fib(n-1) + fib(n-2); return cache[n]

function fib(int $n, array &$memo = []): int
{
    if ($n <= 1) return $n;
    if (isset($memo[$n])) return $memo[$n];
    $memo[$n] = fib($n - 1, $memo) + fib($n - 2, $memo);
    return $memo[$n];
}

echo fib(10); // 55
echo fib(40); // 102334155

Time: O(n) | Space: O(n)

---

Q3. Climbing Stairs [E][LC-70]

Problem: Climb n stairs, taking 1 or 2 steps at a time. How many distinct ways?

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

climbStairs(n) = climbStairs(n-1) + climbStairs(n-2) — exactly Fibonacci!

From stair n, you arrived from stair n-1 (1 step) or stair n-2 (2 steps).

Step 2 — Base cases: n=1 → 1 way; n=2 → 2 ways

Step 3 — Memoize to avoid O(2ⁿ)

function climbStairs(int $n, array &$memo = []): int
{
    if ($n <= 2) return $n;
    if (isset($memo[$n])) return $memo[$n];
    $memo[$n] = climbStairs($n - 1, $memo) + climbStairs($n - 2, $memo);
    return $memo[$n];
}

echo climbStairs(2);  // 2  (1+1, 2)
echo climbStairs(5);  // 8
echo climbStairs(10); // 89

Time: O(n) | Space: O(n)

---

Q4. Reverse String Recursively [E]

Problem: Reverse an array of characters in-place using recursion.

---

🧠 How to Approach This

Step 1 — Recognize the pattern: Two pointer swap, express recursively.

Step 2 — Algorithm: Swap first and last, recurse on inner portion.

function reverseString(array &$chars, int $left = 0, ?int $right = null): void
{
    if ($right === null) $right = count($chars) - 1;
    if ($left >= $right) return;

    [$chars[$left], $chars[$right]] = [$chars[$right], $chars[$left]];
    reverseString($chars, $left + 1, $right - 1);
}

$chars = ['h','e','l','l','o'];
reverseString($chars);
echo implode('', $chars); // "olleh"

Time: O(n) | Space: O(n)

---

Q5. Power Function [M][LC-50]

Problem: Implement pow(x, n) in O(log n).

---

🧠 How to Approach This

Step 1 — Recognize the pattern: Fast exponentiation — divide n by 2 each time.

Step 2 — Even n: x^n = (x^(n/2))² | Odd n: x^n = x × (x^(n/2))²

function myPow(float $x, int $n): float
{
    if ($n === 0)  return 1.0;
    if ($n < 0)    return 1.0 / myPow($x, -$n);
    $half = myPow($x, intdiv($n, 2));
    return ($n % 2 === 0) ? $half * $half : $x * $half * $half;
}

echo myPow(2.0, 10);  // 1024.0
echo myPow(2.0, -3);  // 0.125

Time: O(log n) | Space: O(log n)

---

Q6. Merge Sort [M]

Problem: Sort array using merge sort.

---

🧠 How to Approach This

Step 1 — Divide: Split array in half recursively until single elements.

Step 2 — Conquer: Merge two sorted halves using two-pointer merge.

function mergeSort(array $arr): array
{
    if (count($arr) <= 1) return $arr;
    $mid   = intdiv(count($arr), 2);
    $left  = mergeSort(array_slice($arr, 0, $mid));
    $right = mergeSort(array_slice($arr, $mid));
    $res = []; $i = $j = 0;
    while ($i < count($left) && $j < count($right))
        $res[] = $left[$i] <= $right[$j] ? $left[$i++] : $right[$j++];
    return array_merge($res, array_slice($left, $i), array_slice($right, $j));
}

print_r(mergeSort([5,2,8,1,9,3])); // [1,2,3,5,8,9]

Time: O(n log n) | Space: O(n)

---

Q7. Binary Search (Recursive) [E]

Problem: Search for a target in a sorted array using recursive binary search.

---

🧠 How to Approach This

Step 1: Check mid. If equal → found. If smaller → search right. If larger → search left.

function bSearch(array $arr, int $target, int $lo = 0, ?int $hi = null): int
{
    if ($hi === null) $hi = count($arr) - 1;
    if ($lo > $hi)   return -1;
    $mid = intdiv($lo + $hi, 2);
    if ($arr[$mid] === $target) return $mid;
    return $target < $arr[$mid]
        ? bSearch($arr, $target, $lo, $mid - 1)
        : bSearch($arr, $target, $mid + 1, $hi);
}

echo bSearch([1,3,5,7,9], 7); // 3
echo bSearch([1,3,5,7,9], 4); // -1

Time: O(log n) | Space: O(log n)

---

Q8. Generate All Subsets [M][LC-78]

Problem: Return all subsets of an array with distinct integers.

---

🧠 How to Approach This

Step 1 — Recognize the pattern: For each element: include OR exclude. Binary decision tree.

Step 2 — Algorithm: Recurse from index 0. At each step: add element and recurse, then remove and recurse.

function subsets(array $nums): array
{
    $result = []; $curr = [];
    function bt(array $nums, int $i, array &$curr, array &$result): void {
        if ($i === count($nums)) { $result[] = $curr; return; }
        $curr[] = $nums[$i]; bt($nums, $i+1, $curr, $result);
        array_pop($curr);    bt($nums, $i+1, $curr, $result);
    }
    bt($nums, 0, $curr, $result);
    return $result;
}

print_r(subsets([1,2,3])); // 8 subsets

Time: O(2ⁿ) | Space: O(n)

---

Q9. Generate Permutations [M][LC-46]

Problem: Return all permutations of distinct integers.

---

🧠 How to Approach This

Step 1 — Recognize the pattern: Fix one element at each position via swapping. Swap back after recursion.

function permute(array $nums): array
{
    $result = [];
    function bt(array &$nums, int $start, array &$result): void {
        if ($start === count($nums)) { $result[] = $nums; return; }
        for ($j = $start; $j < count($nums); $j++) {
            [$nums[$start], $nums[$j]] = [$nums[$j], $nums[$start]];
            bt($nums, $start + 1, $result);
            [$nums[$start], $nums[$j]] = [$nums[$j], $nums[$start]];
        }
    }
    bt($nums, 0, $result);
    return $result;
}

print_r(permute([1,2,3])); // 6 permutations

Time: O(n × n!) | Space: O(n)

---

Q10. Combination Sum [M][LC-39]

Problem: Find all combinations that sum to target. Reuse of elements allowed.

---

🧠 How to Approach This

Step 1 — Recognize the pattern: Backtracking with unlimited reuse. Sort first for early pruning.

function combinationSum(array $candidates, int $target): array
{
    sort($candidates); $result = []; $curr = [];
    function bt(array $c, int $t, int $i, array &$curr, array &$result): void {
        if ($t === 0) { $result[] = $curr; return; }
        for ($j = $i; $j < count($c); $j++) {
            if ($c[$j] > $t) break;
            $curr[] = $c[$j];
            bt($c, $t - $c[$j], $j, $curr, $result);
            array_pop($curr);
        }
    }
    bt($candidates, $target, 0, $curr, $result);
    return $result;
}

print_r(combinationSum([2,3,6,7], 7)); // [[2,2,3],[7]]

Time: O(n^(T/M)) | Space: O(T/M)

---

Q11. Subsets II (With Duplicates) [M][LC-90]

Problem: Return all subsets from an array that may contain duplicates. No duplicate subsets.

---

🧠 How to Approach This

Step 1 — Key trick: Sort the array. When iterating choices at the same level, skip duplicates (if nums[i] == nums[i-1] and i > start, skip).

function subsetsWithDup(array $nums): array
{
    sort($nums); $result = []; $curr = [];
    function bt(array $nums, int $i, array &$curr, array &$result): void {
        $result[] = $curr;
        for ($j = $i; $j < count($nums); $j++) {
            if ($j > $i && $nums[$j] === $nums[$j-1]) continue; // skip dup
            $curr[] = $nums[$j];
            bt($nums, $j + 1, $curr, $result);
            array_pop($curr);
        }
    }
    bt($nums, 0, $curr, $result);
    return $result;
}

print_r(subsetsWithDup([1,2,2])); // [[],[1],[1,2],[1,2,2],[2],[2,2]]

Time: O(2ⁿ) | Space: O(n)

---

Q12. Permutations II (With Duplicates) [M][LC-47]

Problem: Return all unique permutations from an array with possible duplicates.

---

🧠 How to Approach This

Step 1 — Key trick: Sort array. Track used indices. Skip if current == previous AND previous is not used (avoids duplicate branches).

function permuteUnique(array $nums): array
{
    sort($nums); $result = []; $curr = [];
    $used = array_fill(0, count($nums), false);
    function bt(array $nums, array &$used, array &$curr, array &$result): void {
        if (count($curr) === count($nums)) { $result[] = $curr; return; }
        for ($i = 0; $i < count($nums); $i++) {
            if ($used[$i]) continue;
            if ($i > 0 && $nums[$i] === $nums[$i-1] && !$used[$i-1]) continue;
            $used[$i] = true; $curr[] = $nums[$i];
            bt($nums, $used, $curr, $result);
            array_pop($curr); $used[$i] = false;
        }
    }
    bt($nums, $used, $curr, $result);
    return $result;
}

echo count(permuteUnique([1,1,2])); // 3 unique permutations

Time: O(n × n!) | Space: O(n)

---

Q13. Letter Combinations of Phone Number [M][LC-17]

Problem: Return all letter combinations for a digit string (T9 keyboard).

---

🧠 How to Approach This

Step 1: Map each digit to letters. For each digit, try each letter, recurse to next digit, backtrack.

function letterCombinations(string $digits): array
{
    if (!$digits) return [];
    $map = ['2'=>'abc','3'=>'def','4'=>'ghi','5'=>'jkl',
            '6'=>'mno','7'=>'pqrs','8'=>'tuv','9'=>'wxyz'];
    $result = []; $curr = '';
    function bt(string $digits, int $i, string &$curr, array $map, array &$result): void {
        if ($i === strlen($digits)) { $result[] = $curr; return; }
        foreach (str_split($map[$digits[$i]]) as $ch) {
            $curr .= $ch;
            bt($digits, $i + 1, $curr, $map, $result);
            $curr = substr($curr, 0, -1);
        }
    }
    bt($digits, 0, $curr, $map, $result);
    return $result;
}

print_r(letterCombinations("23")); // ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Time: O(4ⁿ × n) | Space: O(n)

---

Q14. Generate Parentheses [M][LC-22]

Problem: Generate all valid combinations of n pairs of parentheses.

---

🧠 How to Approach This

Step 1 — Key rules:

- Add '(' if open count < n

- Add ')' if close count < open count

- Base case: length == 2n

function generateParenthesis(int $n): array
{
    $result = []; $curr = '';
    function bt(string &$curr, int $open, int $close, int $n, array &$result): void {
        if (strlen($curr) === 2 * $n) { $result[] = $curr; return; }
        if ($open < $n)     { $curr .= '('; bt($curr, $open+1, $close, $n, $result); $curr = substr($curr,0,-1); }
        if ($close < $open) { $curr .= ')'; bt($curr, $open, $close+1, $n, $result); $curr = substr($curr,0,-1); }
    }
    bt($curr, 0, 0, $n, $result);
    return $result;
}

print_r(generateParenthesis(3)); // ["((()))","(()())","(())()","()(())","()()()"]

Time: O(4ⁿ/√n) | Space: O(n)

---

Q15. Palindrome Partitioning [M][LC-131]

Problem: Partition a string so that every substring is a palindrome. Return all partitions.

---

🧠 How to Approach This

Step 1 — Recognize the pattern: Try every prefix. If it's a palindrome, recurse on the rest.

Step 2 — Pruning: Skip non-palindrome prefixes early.

function partition(string $s): array
{
    $result = []; $curr = [];
    function isPalin(string $s): bool {
        return $s === strrev($s);
    }
    function bt(string $s, int $start, array &$curr, array &$result): void {
        if ($start === strlen($s)) { $result[] = $curr; return; }
        for ($end = $start + 1; $end <= strlen($s); $end++) {
            $sub = substr($s, $start, $end - $start);
            if (isPalin($sub)) {
                $curr[] = $sub;
                bt($s, $end, $curr, $result);
                array_pop($curr);
            }
        }
    }
    bt($s, 0, $curr, $result);
    return $result;
}

print_r(partition("aab")); // [["a","a","b"],["aa","b"]]

Time: O(n × 2ⁿ) | Space: O(n)

---

Q16. N-Queens [H][LC-51]

Problem: Place n non-attacking queens on n×n board. Return all solutions.

---

🧠 How to Approach This

Step 1: Place one queen per row. Check col + both diagonals. Backtrack if no valid column.

function solveNQueens(int $n): array
{
    $result = []; $cols = $diag1 = $diag2 = [];
    $board  = array_fill(0, $n, str_repeat('.', $n));
    function bt(int $row, int $n, array &$board, array &$cols, array &$d1, array &$d2, array &$result): void {
        if ($row === $n) { $result[] = $board; return; }
        for ($col = 0; $col < $n; $col++) {
            if (in_array($col,$cols) || in_array($row-$col,$d1) || in_array($row+$col,$d2)) continue;
            $cols[]=$col; $d1[]=$row-$col; $d2[]=$row+$col;
            $board[$row] = substr_replace($board[$row],'Q',$col,1);
            bt($row+1,$n,$board,$cols,$d1,$d2,$result);
            array_pop($cols); array_pop($d1); array_pop($d2);
            $board[$row] = substr_replace($board[$row],'.',$col,1);
        }
    }
    bt(0,$n,$board,$cols,$diag1,$diag2,$result);
    return $result;
}

echo count(solveNQueens(4)); // 2
echo count(solveNQueens(8)); // 92

Time: O(n!) | Space: O(n)

---

Q17. Sudoku Solver [H][LC-37]

Problem: Fill empty cells in a 9×9 Sudoku grid.

---

🧠 How to Approach This

Step 1: Find empty cell. Try 1-9. Check row/col/box validity. Recurse. If stuck, backtrack (restore '.').

function solveSudoku(array &$board): void
{
    function isValid(array $b, int $r, int $c, string $ch): bool {
        for ($i=0;$i<9;$i++) {
            if ($b[$r][$i]===$ch || $b[$i][$c]===$ch) return false;
            $br=3*intdiv($r,3)+intdiv($i,3); $bc=3*intdiv($c,3)+$i%3;
            if ($b[$br][$bc]===$ch) return false;
        }
        return true;
    }
    function solve(array &$b): bool {
        for ($r=0;$r<9;$r++) for ($c=0;$c<9;$c++) {
            if ($b[$r][$c]!=='.') continue;
            for ($d=1;$d<=9;$d++) {
                if (isValid($b,$r,$c,(string)$d)) {
                    $b[$r][$c]=(string)$d;
                    if (solve($b)) return true;
                    $b[$r][$c]='.';
                }
            }
            return false;
        }
        return true;
    }
    solve($board);
}

Time: O(9^81) worst | Space: O(1)

---

Q18. Word Search [M][LC-79]

Problem: Find if word exists in 2D grid (connected cells, no reuse).

---

🧠 How to Approach This

Step 1: DFS from each matching start cell. Mark visited by replacing char. Restore on backtrack.

function exist(array $board, string $word): bool
{
    $rows=count($board); $cols=count($board[0]);
    function dfs(array &$b, int $r, int $c, string $w, int $i): bool {
        if ($i===strlen($w)) return true;
        if ($r<0||$r>=count($b)||$c<0||$c>=count($b[0])||$b[$r][$c]!==$w[$i]) return false;
        $tmp=$b[$r][$c]; $b[$r][$c]='#';
        $found=dfs($b,$r+1,$c,$w,$i+1)||dfs($b,$r-1,$c,$w,$i+1)||
               dfs($b,$r,$c+1,$w,$i+1)||dfs($b,$r,$c-1,$w,$i+1);
        $b[$r][$c]=$tmp;
        return $found;
    }
    for ($r=0;$r<$rows;$r++) for ($c=0;$c<$cols;$c++)
        if (dfs($board,$r,$c,$word,0)) return true;
    return false;
}

$board=[['A','B','C','E'],['S','F','C','S'],['A','D','E','E']];
var_dump(exist($board,"ABCCED")); // true

Time: O(m×n×4^L) | Space: O(L)

---

Q19. Rat in a Maze [M]

Problem: Find all paths from (0,0) to (n-1,n-1) in a grid where 1=open, 0=blocked.

---

🧠 How to Approach This

Step 1: Move in 4 directions. Mark visited (set to 0). At destination, record path. Restore on backtrack.

function ratMaze(array $maze): array
{
    $n=$n=count($maze); $result=[]; $path=[];
    $dirs=['D'=>[1,0],'L'=>[0,-1],'R'=>[0,1],'U'=>[-1,0]];
    function solve(array &$m, int $r, int $c, int $n, string &$path, array &$result, array $dirs): void {
        if ($r===$n-1&&$c===$n-1) { $result[]=$path; return; }
        foreach ($dirs as $d=>[$dr,$dc]) {
            $nr=$r+$dr; $nc=$c+$dc;
            if ($nr>=0&&$nr<$n&&$nc>=0&&$nc<$n&&$m[$nr][$nc]===1) {
                $m[$nr][$nc]=0; $path.=$d;
                solve($m,$nr,$nc,$n,$path,$result,$dirs);
                $path=substr($path,0,-1); $m[$nr][$nc]=1;
            }
        }
    }
    if ($maze[0][0]===1) { $maze[0][0]=0; solve($maze,0,0,$n,$path,$result,$dirs); }
    return $result;
}

$maze=[[1,0,0,0],[1,1,0,1],[1,1,0,0],[0,1,1,1]];
print_r(ratMaze($maze)); // ["DDRDRR","DRDDRR"]

Time: O(4^(n²)) | Space: O(n²)

---

Q20. Tower of Hanoi [M]

Problem: Print steps to move n disks from rod A to C using B as helper.

function hanoi(int $n, string $from, string $to, string $via): void
{
    if ($n === 1) { echo "Move disk 1: $from → $to\n"; return; }
    hanoi($n-1, $from, $via, $to);
    echo "Move disk $n: $from → $to\n";
    hanoi($n-1, $via, $to, $from);
}
hanoi(3,'A','C','B');

Time: O(2ⁿ) | Space: O(n)

---

Q21. Flood Fill [M][LC-733]

Problem: Starting from (sr,sc), replace all connected cells of same color with new color.

---

🧠 How to Approach This

Step 1: DFS from start cell. Change color, recurse on all 4 neighbors with original color.

function floodFill(array $image, int $sr, int $sc, int $color): array
{
    $orig = $image[$sr][$sc];
    if ($orig === $color) return $image;
    function dfs(array &$img, int $r, int $c, int $orig, int $color): void {
        if ($r<0||$r>=count($img)||$c<0||$c>=count($img[0])||$img[$r][$c]!==$orig) return;
        $img[$r][$c]=$color;
        dfs($img,$r+1,$c,$orig,$color); dfs($img,$r-1,$c,$orig,$color);
        dfs($img,$r,$c+1,$orig,$color); dfs($img,$r,$c-1,$orig,$color);
    }
    dfs($image,$sr,$sc,$orig,$color);
    return $image;
}

Time: O(m×n) | Space: O(m×n)

---

Q22. Count Paths in Grid [M]

Problem: Count unique paths from top-left to bottom-right in m×n grid (only right/down moves).

---

🧠 How to Approach This

Step 1 — Recognize the pattern: paths(r,c) = paths(r+1,c) + paths(r,c+1). Memoize for O(m×n).

function uniquePaths(int $m, int $n, array &$memo = []): int
{
    if ($m === 1 || $n === 1) return 1;
    $key = "$m,$n";
    if (isset($memo[$key])) return $memo[$key];
    $memo[$key] = uniquePaths($m-1,$n,$memo) + uniquePaths($m,$n-1,$memo);
    return $memo[$key];
}

echo uniquePaths(3,7); // 28
echo uniquePaths(3,3); // 6

Time: O(m×n) | Space: O(m×n)

---

Q23. Decode Ways [M][LC-91]

Problem: A string of digits maps to letters (1=A, 26=Z). Count total decode ways.

---

🧠 How to Approach This

Step 1 — Recognize the pattern: At each position, try 1-digit decode and 2-digit decode. Memoize.

Step 2 — Pruning:

- '0' alone → invalid

- Two-digit: must be 10-26

function numDecodings(string $s, int $i = 0, array &$memo = []): int
{
    if ($i === strlen($s)) return 1;   // fully decoded
    if ($s[$i] === '0')   return 0;   // leading zero — invalid
    if (isset($memo[$i])) return $memo[$i];

    // 1-digit decode
    $ways = numDecodings($s, $i + 1, $memo);

    // 2-digit decode (if valid)
    if ($i + 1 < strlen($s)) {
        $twoDigit = (int)substr($s, $i, 2);
        if ($twoDigit >= 10 && $twoDigit <= 26)
            $ways += numDecodings($s, $i + 2, $memo);
    }

    $memo[$i] = $ways;
    return $ways;
}

echo numDecodings("226");  // 3 → (2,2,6), (22,6), (2,26)
echo numDecodings("06");   // 0 → invalid
echo numDecodings("12");   // 2 → (1,2) or (12)

Time: O(n) | Space: O(n)

---

Q24. Restore IP Addresses [M][LC-93]

Problem: Given a string of digits, return all valid IPv4 addresses that can be formed.

---

🧠 How to Approach This

Step 1: 4 parts, each 0-255, no leading zeros. Backtrack with 4 levels of depth.

Step 2 — Pruning:

- Part > 255: invalid

- Leading zero (e.g. "01"): invalid

- Remaining digits can't fit in remaining parts: prune

function restoreIpAddresses(string $s): array
{
    $result = []; $parts = [];
    function bt(string $s, int $start, array &$parts, array &$result): void {
        if (count($parts)===4 && $start===strlen($s)) { $result[]=implode('.',$parts); return; }
        if (count($parts)===4 || $start===strlen($s)) return;
        for ($len=1; $len<=3; $len++) {
            if ($start+$len>strlen($s)) break;
            $seg=substr($s,$start,$len);
            if ($len>1 && $seg[0]==='0') break; // leading zero
            if ((int)$seg > 255) break;
            $parts[]=$seg;
            bt($s,$start+$len,$parts,$result);
            array_pop($parts);
        }
    }
    bt($s,0,$parts,$result);
    return $result;
}

print_r(restoreIpAddresses("25525511135"));
// ["255.255.11.135","255.255.111.35"]

Time: O(3⁴) = O(1) bounded | Space: O(1)

---

Q25. Word Break [M][LC-139]

Problem: Given string s and word dictionary, can s be segmented into dictionary words?

---

🧠 How to Approach This

Step 1 — Recognize the pattern: Try splitting at each position. If prefix is in dict, recurse on rest. Memoize positions.

Step 2 — Memoize: Same starting index may be reached multiple times → cache result.

function wordBreak(string $s, array $wordDict, int $start = 0, array &$memo = []): bool
{
    if ($start === strlen($s)) return true;
    if (isset($memo[$start]))  return $memo[$start];

    for ($end = $start + 1; $end <= strlen($s); $end++) {
        $prefix = substr($s, $start, $end - $start);
        if (in_array($prefix, $wordDict) && wordBreak($s, $wordDict, $end, $memo)) {
            $memo[$start] = true;
            return true;
        }
    }

    $memo[$start] = false;
    return false;
}

var_dump(wordBreak("leetcode",  ["leet","code"]));   // true
var_dump(wordBreak("applepenapple", ["apple","pen"])); // true
var_dump(wordBreak("catsandog", ["cats","dog","sand","cat","an"])); // false

Time: O(n²) | Space: O(n)

---

Summary: Backtracking Decision Guide