---
title: "Бэктрекинг"
url: https://algopath.pro/ru/patterns/backtracking
language: ru
summary: "Сделайте выбор, спуститесь вниз, а потом отмените выбор. Именно отмена позволяет одному массиву держать все варианты подряд."
updated: 2026-08-24
---

# Бэктрекинг

Сделайте выбор, спуститесь вниз, а потом отмените выбор. Именно отмена позволяет одному массиву держать все варианты подряд.

## Бэктрекинг: как это работает?

Держите один массив со сделанными выборами. Это путь вниз по дереву.

На каждом уровне переберите оставшиеся варианты. Каждый вариант это одна ветка.

Добавьте вариант и вызовите себя для следующего уровня. Больше ничего не меняется.

Когда вызов вернулся, снимите вариант обратно. Массив стал ровно таким, каким был.

Внизу запишите копию пути. Запись самого массива сохранит общий буфер.

Обрезайте ветку сразу, как только она обречена. Именно обрезка и даёт скорость.

- `путь = []` Перечисляем подмножества [1, 2]. Пустое уже считается ответом.
- `путь = [1]` Берём единицу и спускаемся на уровень ниже.
- `путь = [1, 2]` Берём и двойку. Эта ветка закончена.
- `путь = [1], потом []` Два снятия отменяют оба выбора. Массив снова пуст.
- `путь = [2]` Пропускаем единицу и берём двойку. Всего четыре подмножества.

## Бэктрекинг: когда применять?

- сгенерировать все подмножества/перестановки/комбинации
- n маленькое (примерно n <= 12-20), экспоненциальный перебор допустим
- сделать выбор, уйти в рекурсию, затем отменить выбор перед следующим
- расставить элементы с ограничениями и откатиться при конфликте (N ферзей, судоку)
- вернуть все допустимые варианты, а не один

## Бэктрекинг: с чем путают?

- **Рекурсия** - Рекурсия спускается и возвращается. Бэктрекинг ещё и возвращает состояние назад при выходе.
- **Рекурсия с мемоизацией** - Кеш окупается, когда аргументы повторяются. На пути из разных выборов это бывает редко.
- **Динамическое программирование (1-D)** - Динамика считает или оптимизирует, ничего не перечисляя. Бэктрекинг нужен, когда нужны сами варианты.
- **Поиск слова в матрице (DFS/backtracking по сетке)** - Это тот же приём на сетке. Выбором там служит, в какого соседа шагнуть.

## Бэктрекинг: сложность по времени и памяти

Ответ растёт экспоненциально, поэтому n маленькое. Подмножеств из 20 элементов 1e6, перестановок из 10 около 3.6e6.

## Бэктрекинг: разбор примера

### Все комбинации, дающие сумму

Даны различные положительные числа и целевая сумма. Перечислите все комбинации, дающие её.

Число можно брать сколько угодно раз.

На каждом уровне пробуйте все числа начиная с текущего индекса.

Старт с текущего индекса не даёт одной комбинации повториться в другом порядке. Отрицательный остаток обрезает ветку.

```javascript
function combinationSum(candidates, target) {
    const result = [];
    const path = [];

    function walk(start, left) {
        if (left === 0) {
            result.push([...path]); // a copy, never the live array
            return;
        }
        if (left < 0) return; // pruned: this branch cannot recover

        for (let i = start; i < candidates.length; i++) {
            path.push(candidates[i]);
            walk(i, left - candidates[i]); // i, not i + 1: reuse is allowed
            path.pop();                    // undo before the next option
        }
    }

    walk(0, target);
    return result;
}
```

## Бэктрекинг: частые ошибки

- **Кладут в ответ живой путь** Тогда все результаты ссылаются на один массив. Кладите его копию.
- **Забывают отменить выбор** Путь растёт и не сокращается. Поздние ветки наследуют чужие выборы.
- **Начинают внутренний цикл с нуля** Тогда одна комбинация появляется во всех возможных порядках. Передавайте текущий индекс вниз.
- **Никогда не обрезают ветки** Без раннего выхода обходится всё дерево целиком. Большинство таких задач быстры именно за счёт обрезки.

## Бэктрекинг: задачи с собеседований

- **Подмножества** Два варианта на элемент: взять или пропустить.
- **Перестановки** На каждом уровне вариант это любой неиспользованный элемент.
- **Комбинации с заданной суммой** Переданный вниз индекс решает, можно ли брать повторно.
- **Ферзи на доске** Обрезка идёт по столбцу и по обеим диагоналям.
- **Поиск слова в сетке** Сетка это дерево, а соседи это варианты.
- **Разбиение на палиндромы** Режьте в каждой позиции, где префикс палиндром.
- **Решатель судоку** Девять вариантов на пустую клетку, обрезанных правилами.

## JavaScript

```javascript
function backtrack(path, choices, result) {
    if (path.length === choices.length) { // or another stop condition
        result.push([...path]);
        return;
    }
    for (const choice of choices) {
        path.push(choice); // choose
        backtrack(path, choices, result); // explore
        path.pop(); // undo
    }
}
```

## Python

```python
def backtrack(path, choices, result):
    if len(path) == len(choices):  # or another stop condition
        result.append(path[:])
        return
    for choice in choices:
        path.append(choice)  # choose
        backtrack(path, choices, result)  # explore
        path.pop()  # undo
```

## PHP

```php
function backtrack(array &$path, array $choices, array &$result): void {
    if (count($path) === count($choices)) {
        $result[] = $path;
        return;
    }
    foreach ($choices as $choice) {
        $path[] = $choice; // choose
        backtrack($path, $choices, $result); // explore
        array_pop($path); // undo
    }
}
```