Что такое поиск с возвратом (backtracking) на примере генерации перестановок?

Backtracking — обход дерева решений в глубину: делаем выбор, рекурсивно продолжаем, затем отменяем выбор и пробуем следующий, отсекая ветки, которые заведомо не ведут к ответу.

Шаблон

1. Если частичное решение полное — сохранить копию.
2. Для каждого допустимого варианта: выбрать → рекурсия → откатить.
3. Отсечение (pruning): не спускаться в ветку, если ограничение уже нарушено.

const permutations = (nums) => {
  const res = [], path = [], used = new Array(nums.length).fill(false);
  const backtrack = () => {
    if (path.length === nums.length) {
      res.push([...path]);
      return;
    }
    for (const [i, x] of nums.entries()) {
      if (used[i]) continue;
      used[i] = true;
      path.push(x);
      backtrack();
      path.pop();
      used[i] = false;
    }
  };
  backtrack();
  return res;
};

Сложность

• Перестановок n!, копирование каждой — O(n), итого O(n·n!); при n = 10 это уже 3.6 млн вариантов.
• Для подмножеств — O(n·2ⁿ), для N ферзей отсечения по столбцам и диагоналям сокращают перебор на порядки.

Типичные ошибки

• res.push(path) без копии — в результате окажутся ссылки на один и тот же (в итоге пустой) массив.
• Забытый откат состояния (used[i] = false) — ветки «видят» чужие выборы.

Коротко для собеседования

Backtracking перебирает варианты рекурсивно и после каждой ветки откатывает сделанный выбор, а отсечения не дают спускаться в заведомо плохие ветки. Сложность остаётся экспоненциальной, так что он годится для небольших n; классические ошибки — сохранить путь без копии и забыть откат.