↩️ Backtracking

// Generic Backtracking Template
function backtrack(state, choices, result):
    if satisfied(state):
        result.add(copy(state))
        return

    for each choice in choices:
        if isValid(state, choice):
            apply(state, choice)
            backtrack(state, choices, result)
            undo(state, choice)  // ← THE "BACKTRACK" STEP!

function solveNQueens(int $n): array {
    $result = [];
    $board = array_fill(0, $n, array_fill(0, $n, '.'));
    backtrack($board, 0, $n, $result);
    return $result;
}

function backtrack(array &$board, int $row, int $n, array &$result): void {
    if ($row === $n) {
        $result[] = array_map(fn($r) => implode('', $r), $board);
        return;
    }

    for ($col = 0; $col < $n; $col++) {
        if (isSafe($board, $row, $col, $n)) {
            $board[$row][$col] = 'Q';            // Place queen
            backtrack($board, $row + 1, $n, $result);
            $board[$row][$col] = '.';            // ← BACKTRACK!
        }
    }
}

function isSafe(array $board, int $row, int $col, int $n): bool {
    // Check column above
    for ($i = 0; $i < $row; $i++)
        if ($board[$i][$col] === 'Q') return false;
    // Check upper-left diagonal
    for ($i=$row-1,$j=$col-1; $i>=0&&$j>=0; $i--,$j--)
        if ($board[$i][$j] === 'Q') return false;
    // Check upper-right diagonal
    for ($i=$row-1,$j=$col+1; $i>=0&&$j<$n; $i--,$j++)
        if ($board[$i][$j] === 'Q') return false;
    return true;
}

print_r(solveNQueens(4));
// 2 solutions for n=4, 92 for n=8

function subsets(array $nums): array {
    $result = []; $current = [];
    backtrackSubsets($nums, 0, $current, $result);
    return $result;
}

function backtrackSubsets(array $nums, int $start, array &$current, array &$result): void {
    $result[] = $current; // Add current subset

    for ($i = $start; $i < count($nums); $i++) {
        $current[] = $nums[$i];        // Include nums[i]
        backtrackSubsets($nums, $i + 1, $current, $result);
        array_pop($current);           // ← BACKTRACK!
    }
}

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

function permute(array $nums): array {
    $result = []; $used = array_fill(0, count($nums), false);
    backtrackPermute($nums, [], $used, $result);
    return $result;
}

function backtrackPermute(array $nums, array $current, array &$used, array &$result): void {
    if (count($current) === count($nums)) {
        $result[] = $current; return;
    }
    for ($i = 0; $i < count($nums); $i++) {
        if ($used[$i]) continue;
        $used[$i] = true;
        $current[] = $nums[$i];
        backtrackPermute($nums, $current, $used, $result);
        array_pop($current);
        $used[$i] = false;             // ← BACKTRACK!
    }
}