Что такое backtracking?

Question

Accepted Answer

**Backtracking** строит потенциальные решения пошагово и **отказывает** от частичного кандидата, как только он не может привести к допустимому решению. Он систематически исследует пространство решений через DFS, отсекая тупики.

## Идея

Выбери -> исследуй -> отмени выбор. Попробуй вариант, рекурсия; если не сработает, откатись и пробуй следующий.

## Пример: все перестановки

```python
def permutations(nums):
    result = []
    def backtrack(path, remaining):
        if not remaining:              # complete solution
            result.append(path[:])
            return
        for i in range(len(remaining)):
            path.append(remaining[i])              # choose
            backtrack(path, remaining[:i] + remaining[i+1:])  # explore
            path.pop()                             # un-choose (backtrack)
    backtrack([], nums)
    return result

permutations([1, 2, 3])   # -> 6 permutations
```

## Классические задачи

- **Задача N-ферзей**, Судоку, ход коня.
- **Подмножества / комбинации / перестановки.**
- **Поиск слова**, решение лабиринта.

## Сложность

Часто экспоненциальная (например, O(n!) для перестановок), но **отсечение** кардинально сокращает практический поиск.

## Когда использовать / ловушки

Используй для задач удовлетворения ограничений и "найти все допустимые конфигурации". Ключевой выигрыш — **раннее отсечение** — пропускай ветви, нарушающие ограничения. Забыть отменить состояние ("отмени выбор") — классическая ошибка.

## Почему это важно

Backtracking — это систематический способ исследовать комбинаторные пространства без пропусков и повторений кандидатов.

Хорошее отсечение превращает неподъёмный brute force в алгоритм, завершающийся за разумное время.

Он лежит в основе решателей для головоломок, планирования и задач с ограничениями по всей индустрии.