MidПрактика16 min

Backtracking

Перебор с откатом: subsets, permutations, combinations, N-Queens

AlgoInterview patterns

Backtracking (перебор с откатом)

Идея

Backtracking — это систематический перебор всех возможных решений с откатом при обнаружении тупика. Строим решение пошагово, отменяя последний шаг если он ведёт к невалидному состоянию.

Дерево решений для подмножеств {1, 2, 3}:

                    []
              /     |      \
           [1]     [2]     [3]
          /   \     |
       [1,2] [1,3] [2,3]
         |
      [1,2,3]

Шаблон Backtracking

<?php
declare(strict_types=1);

function backtrack(array &$state, array $choices, array &$result): void
{
    if (isSolution($state)) {
        $result[] = $state; // Save solution (copy by value)
        return;
    }

    foreach ($choices as $choice) {
        if (isValid($choice, $state)) {
            $state[] = $choice;                    // Make choice
            backtrack($state, $newChoices, $result); // Recurse
            array_pop($state);                     // Undo (backtrack)
        }
    }
}
## Задача 1: Subsets (все подмножества) 
<?php
declare(strict_types=1);

/**
 * @param list<int> $nums
 * @return list<list<int>>
 */
function subsets(array $nums): array
{
    $result = [];

    $backtrack = function (int $start, array $current) use (&$backtrack, &$result, $nums): void {
        $result[] = $current; // Every state is a solution

        for ($i = $start; $i < count($nums); $i++) {
            $current[] = $nums[$i];
            $backtrack($i + 1, $current);
            array_pop($current); // Undo
        }
    };

    $backtrack(0, []);
    return $result;
}

// nums = [1, 2, 3]
// Result: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]
### Subsets II (с дубликатами) 
<?php
declare(strict_types=1);

/**
 * @param list<int> $nums
 * @return list<list<int>>
 */
function subsetsWithDup(array $nums): array
{
    sort($nums); // Sort to group duplicates
    $result = [];

    $backtrack = function (int $start, array $current) use (&$backtrack, &$result, $nums): void {
        $result[] = $current;

        for ($i = $start; $i < count($nums); $i++) {
            if ($i > $start && $nums[$i] === $nums[$i - 1]) {
                continue; // Skip duplicates
            }
            $current[] = $nums[$i];
            $backtrack($i + 1, $current);
            array_pop($current);
        }
    };

    $backtrack(0, []);
    return $result;
}
## Задача 2: Permutations (все перестановки) 
<?php
declare(strict_types=1);

/**
 * @param list<int> $nums
 * @return list<list<int>>
 */
function permutations(array $nums): array
{
    $result = [];

    $backtrack = function (array $current, array $remaining) use (&$backtrack, &$result): void {
        if ($remaining === []) {
            $result[] = $current;
            return;
        }

        for ($i = 0; $i < count($remaining); $i++) {
            $current[] = $remaining[$i];
            $newRemaining = array_merge(array_slice($remaining, 0, $i), array_slice($remaining, $i + 1));
            $backtrack($current, $newRemaining);
            array_pop($current);
        }
    };

    $backtrack([], $nums);
    return $result;
}

// nums = [1, 2, 3]
// Result: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
Альтернатива через swap: 
<?php
declare(strict_types=1);

/**
 * @param list<int> $nums
 * @return list<list<int>>
 */
function permutationsSwap(array $nums): array
{
    $result = [];

    $backtrack = function (int $start) use (&$backtrack, &$result, &$nums): void {
        if ($start === count($nums)) {
            $result[] = $nums; // Copy by value
            return;
        }

        for ($i = $start; $i < count($nums); $i++) {
            [$nums[$start], $nums[$i]] = [$nums[$i], $nums[$start]];
            $backtrack($start + 1);
            [$nums[$start], $nums[$i]] = [$nums[$i], $nums[$start]];
        }
    };

    $backtrack(0);
    return $result;
}
## Задача 3: Combinations 
<?php
declare(strict_types=1);

/**
 * @return list<list<int>>
 */
function combine(int $n, int $k): array
{
    $result = [];

    $backtrack = function (int $start, array $current) use (&$backtrack, &$result, $n, $k): void {
        if (count($current) === $k) {
            $result[] = $current;
            return;
        }

        // Optimization: stop if not enough elements remain
        for ($i = $start; $i <= $n - ($k - count($current)) + 1; $i++) {
            $current[] = $i;
            $backtrack($i + 1, $current);
            array_pop($current);
        }
    };

    $backtrack(1, []);
    return $result;
}

// n=4, k=2
// Result: [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]
## Задача 4: Combination Sum 
<?php
declare(strict_types=1);

/**
 * @param list<int> $candidates
 * @return list<list<int>>
 */
function combinationSum(array $candidates, int $target): array
{
    $result = [];

    $backtrack = function (int $start, array $current, int $remaining) use (&$backtrack, &$result, $candidates): void {
        if ($remaining === 0) {
            $result[] = $current;
            return;
        }
        if ($remaining < 0) {
            return;
        }

        for ($i = $start; $i < count($candidates); $i++) {
            $current[] = $candidates[$i];
            $backtrack($i, $current, $remaining - $candidates[$i]); // $i, not $i+1 (repeats!)
            array_pop($current);
        }
    };

    $backtrack(0, [], $target);
    return $result;
}

// candidates = [2, 3, 6, 7], target = 7
// [[2,2,3], [7]]
## Задача 5: N-Queens 
<?php
declare(strict_types=1);

/**
 * @return list<list<string>>
 */
function solveNQueens(int $n): array
{
    $result = [];
    $board = array_fill(0, $n, str_repeat('.', $n));

    $cols = [];
    $diag1 = []; // row - col
    $diag2 = []; // row + col

    $backtrack = function (int $row) use (&$backtrack, &$result, &$board, &$cols, &$diag1, &$diag2, $n): void {
        if ($row === $n) {
            $result[] = $board;
            return;
        }

        for ($col = 0; $col < $n; $col++) {
            if (isset($cols[$col]) || isset($diag1[$row - $col]) || isset($diag2[$row + $col])) {
                continue;
            }

            $board[$row][$col] = 'Q';
            $cols[$col] = true;
            $diag1[$row - $col] = true;
            $diag2[$row + $col] = true;

            $backtrack($row + 1);

            $board[$row][$col] = '.';
            unset($cols[$col], $diag1[$row - $col], $diag2[$row + $col]);
        }
    };

    $backtrack(0);
    return $result;
}
Визуализация для N=4: 
Решение 1:        Решение 2:
. Q . .           . . Q .
. . . Q           Q . . .
Q . . .           . . . Q
. . Q .           . Q . .

<?php
declare(strict_types=1);

/**
 * @param list<list<string>> $board
 */
function exist(array &$board, string $word): bool
{
    $rows = count($board);
    $cols = count($board[0]);

    $backtrack = function (int $r, int $c, int $idx) use (&$backtrack, &$board, $rows, $cols, $word): bool {
        if ($idx === strlen($word)) {
            return true;
        }

        if ($r < 0 || $r >= $rows || $c < 0 || $c >= $cols
            || $board[$r][$c] !== $word[$idx]) {
            return false;
        }

        $temp = $board[$r][$c];
        $board[$r][$c] = '#'; // Mark as visited

        $found = $backtrack($r + 1, $c, $idx + 1)
              || $backtrack($r - 1, $c, $idx + 1)
              || $backtrack($r, $c + 1, $idx + 1)
              || $backtrack($r, $c - 1, $idx + 1);

        $board[$r][$c] = $temp; // Undo
        return $found;
    };

    for ($r = 0; $r < $rows; $r++) {
        for ($c = 0; $c < $cols; $c++) {
            if ($backtrack($r, $c, 0)) {
                return true;
            }
        }
    }
    return false;
}
## Оптимизация: Pruning (отсечение) 
<?php
declare(strict_types=1);

// Without pruning: check all branches
// With pruning: cut obviously invalid branches

// Example in Combination Sum:
/**
 * @param list<int> $candidates
 * @return list<list<int>>
 */
function combinationSumPruned(array $candidates, int $target): array
{
    sort($candidates); // Sort for pruning
    $result = [];

    $backtrack = function (int $start, array $current, int $remaining) use (&$backtrack, &$result, $candidates): void {
        if ($remaining === 0) {
            $result[] = $current;
            return;
        }

        for ($i = $start; $i < count($candidates); $i++) {
            if ($candidates[$i] > $remaining) {
                break; // Pruning! All further elements are larger
            }
            $current[] = $candidates[$i];
            $backtrack($i, $current, $remaining - $candidates[$i]);
            array_pop($current);
        }
    };

    $backtrack(0, [], $target);
    return $result;
}
## Шпаргалка: какой шаблон использовать
Задача start с i+1? Повторы? Сортировка?
Subsets i + 1 Нет Нет
Subsets II i + 1 Skip dup Да
Permutations Все элементы Нет Нет
Combinations i + 1 Нет Нет
Combination Sum i (повторы) Да Да (pruning)

Запомни: Backtracking = рекурсия + выбор + откат. Три ключевых вопроса: 1) Что является решением? (базовый случай) 2) Какие выборы на каждом шаге? (цикл) 3) Как откатить? (pop/remove). Pruning ускоряет в разы: отсекай невалидные ветви как можно раньше.

Итоги

  1. Backtracking = DFS по дереву решений
  2. Шаблон: выбор -> рекурсия -> откат
  3. Subsets: добавляй каждое состояние в результат
  4. Permutations: используй все элементы, без start
  5. N-Queens: sets для столбцов и диагоналей
  6. Pruning: сортировка + break при невалидном условии

Проверь себя

В задаче N-Queens, зачем нужны три множества: cols, diag1 (row-col), diag2 (row+col)?

В задаче Combination Sum с candidates = [2, 3, 6, 7] и target = 7, почему рекурсивный вызов использует `$i` а не `$i + 1`?

Что такое pruning (отсечение) в backtracking и какой эффект оно даёт?

Как в Subsets II (с дубликатами) избегают повторных подмножеств?

Сколько подмножеств (subsets) у множества [1, 2, 3]?

Связанные темы

Паттерн Sliding Window

Связанная тема

Prefix Sum

Связанная тема

Монотонный стек

Связанная тема

Жадные алгоритмы

Связанная тема