Backtracking (Поиск с возвратом)
Когда применять:
- Нужно найти все возможные комбинации, перестановки или подмножества.
- Задача решается полным перебором (Brute Force), но с возможностью отсечения ветвей.
- Судоку, N-Queens, генерация скобок.
Ключевая идея: Choose -> Explore -> Unchoose
Шаблон: Permutations / Subsets
const result = [];
function backtrack(path, start, options) {
// 1. Base Case: условие добавления в ответ
// (для перестановок: path.length === nums.length)
result.push([...path]); // Важно делать копию массива!
for (let i = start; i < options.length; i++) {
// Optional: Pruning (отсечение)
// if (path.includes(options[i])) continue;
// 2. Choose (Выбираем)
path.push(options[i]);
// 3. Explore (Рекурсия)
backtrack(path, i + 1, options); // i + 1 для комбинаций без повторов
// 4. Unchoose (Отменяем выбор для следующей итерации)
path.pop();
}
}