Бэктрекинг простым языком: как перебирать варианты и не сойти с ума

Что это такое

Бэктрекинг — это систематический перебор вариантов, в котором мы строим решение по шагам, а как только понимаем, что текущий путь тупиковый, откатываемся назад и пробуем другой.

Бытовая аналогия — лабиринт. Идёте по коридору, упёрлись в стену, вернулись к последней развилке, свернули в другую сторону. Никакого волшебства, но есть важная деталь: возвращаясь, вы стираете за собой пометки, иначе следующий путь будет считать эти коридоры пройденными.

Именно это стирание — то место, где чаще всего ошибаются. Всё остальное в бэктрекинге механика.

Универсальный шаблон

Почти любая задача на перебор с возвратом укладывается в одну форму:

function backtrack(path, choices) {
  // 1. база: решение собрано целиком
  if (isComplete(path)) {
    result.push([...path]); // копия! о ней ниже
    return;
  }

  // 2. перебираем варианты на текущем шаге
  for (const choice of choices) {
    if (!isValid(path, choice)) continue; // отсечение

    path.push(choice);              // делаем выбор
    backtrack(path, nextChoices);   // идём глубже
    path.pop();                     // ОТКАТ — снимаем выбор
  }
}

Три строки в конце — сердце техники. «Выбрали → углубились → отменили выбор». Забудете pop — состояние протечёт в соседние ветви, и ответ будет мусорным.

Про копию в базовом случае. path — один и тот же массив на протяжении всей рекурсии, мы его постоянно мутируем. Если положить в результат ссылку, то к концу работы все элементы результата окажутся ссылками на один пустой массив. Копия обязательна.

Задача первая: все подмножества

Дан массив уникальных чисел, нужно вернуть все подмножества.

[1, 2, 3] → [], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]

На каждом шаге решаем: взять текущий элемент или пропустить.

function subsets(nums) {
  const result = [];
  const path = [];

  function backtrack(start) {
    // каждый узел рекурсии — готовое подмножество
    result.push([...path]);

    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      backtrack(i + 1); // i + 1: не берём один элемент дважды
      path.pop();
    }
  }

  backtrack(0);
  return result;
}

Параметр start — ключевой. Он гарантирует, что мы двигаемся только вперёд и не порождаем [1,2] и [2,1] как разные ответы. Для подмножеств порядок не важен, поэтому дубликаты нужно отсечь именно так.

Сложность — O(2ⁿ · n): подмножеств 2ⁿ, копирование каждого стоит O(n).

Задача вторая: перестановки

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

function permute(nums) {
  const result = [];
  const path = [];
  const used = new Array(nums.length).fill(false);

  function backtrack() {
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }

    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;

      used[i] = true;
      path.push(nums[i]);

      backtrack();

      path.pop();
      used[i] = false; // откатываем ОБА изменения
    }
  }

  backtrack();
  return result;
}

permute([1, 2, 3]);
// [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

Обратите внимание: откатывать надо всё, что меняли. Здесь два изменения — path и used, и оба возвращаются в исходное состояние. Забытый used[i] = false — вторая по популярности ошибка после забытого pop.

Сложность — O(n! · n).

Отсечение: то, ради чего всё затевается

Голый перебор экспоненциален. Бэктрекинг становится практичным, когда мы рано отбрасываем заведомо тупиковые ветви.

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

function combinationSum(candidates, target) {
  const result = [];
  const path = [];
  // сортировка нужна для отсечения ниже
  const sorted = [...candidates].sort((a, b) => a - b);

  function backtrack(start, remaining) {
    if (remaining === 0) {
      result.push([...path]);
      return;
    }

    for (let i = start; i < sorted.length; i++) {
      // массив отсортирован: если не влезло это число,
      // все следующие тем более не влезут
      if (sorted[i] > remaining) break;

      path.push(sorted[i]);
      backtrack(i, remaining - sorted[i]); // i, а не i+1 — можно повторять
      path.pop();
    }
  }

  backtrack(0, target);
  return result;
}

combinationSum([2, 3, 6, 7], 7);
// [[2, 2, 3], [7]]

Строка if (sorted[i] > remaining) break; — и есть отсечение. Без неё алгоритм честно спустится в ветвь, наберёт отрицательный остаток и только там поймёт, что зря. С сортировкой мы обрываем не одну ветвь, а сразу все оставшиеся на этом уровне — поэтому break, а не continue.

На реальных данных такое отсечение ускоряет решение в разы. Умение находить подобные условия — главное, что отличает рабочий бэктрекинг от учебного.

Классика: N ферзей

Расставить N ферзей на доске N×N так, чтобы они не били друг друга. Задача, на которой бэктрекинг обычно и объясняют.

Ставим по одному ферзю в каждую строку, для каждой перебираем столбцы.

function solveNQueens(n) {
  const result = [];
  const queens = []; // queens[row] = столбец

  function isSafe(row, col) {
    for (let r = 0; r < row; r++) {
      const c = queens[r];
      // тот же столбец или та же диагональ
      if (c === col || Math.abs(r - row) === Math.abs(c - col)) {
        return false;
      }
    }
    return true;
  }

  function backtrack(row) {
    if (row === n) {
      result.push(
        queens.map((c) => '.'.repeat(c) + 'Q' + '.'.repeat(n - c - 1))
      );
      return;
    }

    for (let col = 0; col < n; col++) {
      if (!isSafe(row, col)) continue;

      queens.push(col);
      backtrack(row + 1);
      queens.pop();
    }
  }

  backtrack(0);
  return result;
}

solveNQueens(4).length; // 2

Проверка диагонали через Math.abs(r - row) === Math.abs(c - col) — приём, который стоит запомнить: два поля лежат на одной диагонали, если разность строк по модулю равна разности столбцов.

Строку проверять не нужно вовсе: мы ставим ровно одного ферзя на строку по построению. Это тоже форма отсечения — сузили пространство перебора самой схемой решения.

Как оценивать сложность

Формула простая: (количество вариантов на шаге)^(глубина) × (стоимость обработки листа).

Отсечения на асимптотику обычно не влияют — она остаётся экспоненциальной. Но на практике разница между «работает сорок минут» и «работает две десятых секунды» определяется именно ими. На собеседовании честно говорите: «в худшем случае экспонента, но отсечение по сумме отбрасывает большую часть дерева».

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

Забытый откат. Самая частая. Симптом — в результате накапливается мусор из предыдущих ветвей.

Ссылка вместо копии в результате. Симптом — все элементы ответа одинаковые, обычно пустые.

Откат не всех изменений. Меняли два состояния, вернули одно.

Неправильный старт в рекурсии. backtrack(i) разрешает повторное использование элемента, backtrack(i + 1) — запрещает. Перепутать легко, а тесты на маленьких входах могут это не поймать.

Дубликаты при повторяющихся элементах. Если во входе есть одинаковые числа, стандартный шаблон выдаст повторы. Лечится сортировкой и пропуском: if (i > start && nums[i] === nums[i - 1]) continue;.

Когда применять

Бэктрекинг — это ответ на задачи, где просят все варианты, а не один оптимальный:

• перечислить все подмножества, перестановки, комбинации;
• расставить объекты с ограничениями (ферзи, судоку, раскраска графа);
• найти все пути в лабиринте или слово в матрице;
• разбить строку всеми возможными способами.

Слова-маркеры в условии: «найдите все», «перечислите», «сколькими способами» с необходимостью выписать сами способы.

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

Что запомнить

• Шаблон один: выбрали → углубились → откатили.
• Копируйте path при записи в результат.
• Откатывайте все изменения состояния, а не только очевидное.
• start в цикле контролирует, важен ли порядок и можно ли повторять элементы.
• Отсечение не меняет асимптотику, но решает, будет ли код работать на реальных данных.

Закрепите на практике

Две задачи закроют тему: комбинации с заданной суммой (тренирует отсечение) и поиск слова в матрице символов (тренирует откат состояния на сетке). Вторая особенно полезна — там нужно помечать посещённые клетки и обязательно снимать пометку при возврате.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→