001 Перебор с возвратом Backtracking

Перебор с возвратом (backtracking) — это метод решения задач, основанный на переборе всех возможных вариантов, используя рекурсию и откаты (возврат), когда текущий вариант оказывается неудачным. Этот подход эффективен для решения задач, где требуется найти все возможные решения или оптимальное решение среди множества вариантов.

Основные Принципы
Рекурсия: Метод используется для исследования всех возможных путей решения. На каждом шаге алгоритм принимает решение о том, какое действие предпринять.

Откат: Если текущее действие приводит к некорректному состоянию или не приводит к решению, алгоритм откатывается к предыдущему состоянию и пробует другой путь.

Принципы отсечения: Для повышения эффективности перебора часто применяются методы отсечения, которые позволяют избегать дальнейшего исследования путей, которые уже доказано не могут привести к решению.