Паттерн: Перебор с возвратом

Признак в условии

• «все подмножества / перестановки / комбинации»
• «расставить так, чтобы не конфликтовали»
• ответ - не число, а список вариантов

Каркас

const walk = (позиция, текущее) => {
  if (готово) { out.push([...текущее]); return; }   // КОПИЯ, не ссылка
  for (const вариант of варианты(позиция)) {
    if (!допустим(вариант)) continue;              // отсечение
    текущее.push(вариант);
    walk(позиция + 1, текущее);
    текущее.pop();                                 // откат
  }
};

Два ключевых решения

Копия при сохранении: out.push([...current]) - иначе в результат попадут ссылки на один массив, который в конце опустеет. Параметр start отсекает перестановки одного набора: walk(i, …) разрешает повтор элемента, walk(i + 1, …) запрещает.

Сложность

Экспоненциальная: подмножества O(2ⁿ·n), перестановки O(n!·n). Отсечения решают, будет ли это работать на практике.

Частые ошибки

• сохранение без копии
• откатывается массив, но не флаг «использовано»
• нет отсечения, и дерево перебора взрывается
• без start в результате появляются перестановки одного набора

Мнемоника

«Выбрал, углубился, откатил»

Не путать с

• Обход в глубину - возврат нужен там, где после ветки состояние надо откатить: убрать элемент из текущего набора, снять пометку
• Динамическое программирование - если подзадачи повторяются, перебор превращается в динамику запоминанием; если нет - остаётся перебором

Задачи на этот паттерн

• все подмножества
• все перестановки
• наборы с заданной суммой
• правильные скобочные последовательности
• буквы номера телефона
• поиск слова в сетке

Суть

Backtracking строит решение по шагам и обходит дерево всех вариантов: делает выбор, идёт глубже, отменяет выбор. Это честный перебор, поэтому применим при маленьких n и нужен, когда просят все варианты.

Как распознать по условию

• «все подмножества / перестановки / комбинации / разбиения»;
• «все пути», «расставь ферзей», «судоку», «слово в сетке»;
• n до 10-20;
• ответ сам по себе экспоненциального размера.

Если нужно не перечислить, а посчитать или найти лучший вариант, сначала подумай о динамике.

Шаблон

function backtrack(nums) {
  const res = [], path = [];
  function go(start) {
    res.push([...path]);                // копия!
    for (let j = start; j < nums.length; j++) {
      path.push(nums[j]);               // выбор
      go(j + 1);                        // исследование
      path.pop();                       // отмена
    }
  }
  go(0);
  return res;
}

Это подмножества. Вариации:

• Сочетания по k: сохраняем только при path.length === k, for с start.
• Перестановки: for по всем, массив used.
• Сумма комбинаций с повтором элемента: go(j) вместо go(j + 1).
• Дубликаты во входе: сортировка и if (j > start && nums[j] === nums[j - 1]) continue.

Отсечения

Главный способ ускорить перебор: бросать ветку, как только она не может дать ответ. Сумма уже больше target, ферзь бьётся, буква не совпала. После сортировки часто можно делать break вместо continue.

Сложность

Задача	Число вариантов	Время
подмножества	2ⁿ	O(n · 2ⁿ)
перестановки	n!	O(n · n!)
сочетания из n по k	C(n, k)	O(k · C(n, k))

Память: O(n) на путь и стек, плюс ответ.

Ловушки

• res.push(path) без копии: в ответе одинаковые пустые массивы.
• Забыть отмену выбора.
• Неверный пропуск дубликатов (без j > start).
• Мутация входной сетки без восстановления в поиске слова.

Что спросят на собесе

• Сгенерируй все подмножества и назови сложность.
• Чем перестановки отличаются от сочетаний в коде?
• Как убрать дубликаты, если во входе повторы?
• Какие отсечения можно добавить?