Бэктрекинг

O(2^n)/O(n!)

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

Сигналы

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

Шаблон

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
    }
}

Похоже, но не то

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

n маленькое (n <= 12-20, пространство поиска экспоненциальное) -> O(2^n) для подмножеств или O(n!) для перестановок, в каждой ветке O(1)-O(n) работы на выбор и отмену.

Изучить этот паттерн