Перейти к содержимому
Algorithms & Data Structures Interview Tutorial

Рекурсия и Backtracking

Рекурсия — функция, решающая задачу через вызов самой себя на меньшей подзадаче, с базовым случаем для остановки. Это фундаментальный инструмент в Computer Science: любой итеративный алгоритм можно переписать рекурсивно (и наоборот, через стек), но рекурсия часто более естественна для задач с деревьями, графами, комбинаторикой. Backtracking — это рекурсия с откатом: мы строим решение шаг за шагом (добавляя элементы в текущий путь), рекурсивно исследуем дальше, затем откатываем последнее изменение (убираем элемент) и пробуем следующий вариант. По сути, это DFS по дереву решений с явным построением и разрушением состояния.

Канонический шаблон backtracking: choose → explore → unchoose. (1) Choose — добавляем элемент в текущее решение (path.push, used[i]=true). (2) Explore — рекурсивный вызов для продолжения построения. (3) Unchoose — откатываем изменение (path.pop, used[i]=false). Без отката следующая итерация цикла увидит “грязное” состояние с предыдущими выборами. Критически важно: если передаём объект/массив по ссылке, нужно копировать при сохранении в результат: result.push([...path]), иначе все решения в result будут указывать на один и тот же массив.

Когда применять / Мотивация

Заголовок раздела «Когда применять / Мотивация»

Канонический шаблон backtracking: choose → explore → unchoose. (1) Choose — добавляем элемент в текущее решение (path.push, used[i]=true). (2) Explore — рекурсивный вызов для продолжения построения. (3) Unchoose — откатываем изменение (path.pop, used[i]=false). Без отката следующая итерация цикла увидит “грязное” состояние с предыдущими выборами. Критически важно: если передаём объект/массив по ссылке, нужно копировать при сохранении в результат: result.push([...path]), иначе все решения в result будут указывать на один и тот же массив.

Идея / Как работает

Заголовок раздела «Идея / Как работает»

Когда применять: Сигналы в условии: “найти все возможные”, “выведите все способы”, “генерируйте все комбинации/перестановки/разбиения”, “solve puzzle (Sudoku, N-Queens)”. Backtracking перебирает экспоненциальное пространство (часто 2ⁿ или n!), но pruning (отсечение невалидных веток) делает реальную сложность приемлемой. Примеры: Permutations (n!), Subsets (2ⁿ), Combination Sum (экспоненциально, но ограничено target), N-Queens (фактически ~n! с отсечениями, но алгоритмически эффективнее полного перебора).

Оптимизации: (1) Pruning — проверка валидности текущего пути до рекурсивного вызова: если текущий выбор заведомо не приведёт к решению → skip (continue). Например, в N-Queens проверяем атаки до вызова рекурсии. (2) Сортировка выборов — иногда порядок выборов влияет на эффективность отсечений (например, в Combination Sum сортируем кандидаты, чтобы раньше отсекать большие значения). (3) Мемоизация — если подзадачи повторяются (одинаковые аргументы рекурсии), кешируем результаты → переход к DP. Пример: Word Break II с мемоизацией (без неё — экспоненциально, с ней — полиномиально в зависимости от количества уникальных состояний).

Реализация

Заголовок раздела «Реализация»

Задача: Combination Sum (LeetCode 39). Дан массив уникальных кандидатов candidates и целевое число target. Найти все уникальные комбинации кандидатов, сумма которых равна target. Один и тот же кандидат может использоваться неограниченно. Например, candidates = [2,3,6,7], target = 7 → [[2,2,3], [7]].

Подход: Это классический backtracking: строим комбинацию, добавляя по одному кандидату, рекурсивно ищем дальше, откатываем. Для избежания дубликатов (например, [2,3] и [3,2] — это одна комбинация) передаём start-индекс: на каждом уровне рекурсии рассматриваем только кандидаты начиная с start. Для повторного использования кандидата передаём тот же start (не start+1). Базовый случай: если target == 0 → нашли комбинацию, добавляем копию в результат. Если target < 0 → отсечение (pruning), эта ветка не приведёт к решению. Оптимизация: если отсортировать candidates, можем досрочно выйти из цикла, когда candidates[i] > target (все последующие тоже > target).

function combinationSum(candidates, target) {
    const result = [];
    candidates.sort((a, b) => a - b); // для pruning


    function backtrack(start, path, remaining) {
      // Базовый случай: нашли комбинацию
      if (remaining === 0) {
        result.push([...path]); // ВАЖНО: копируем path
        return;
      }


      // Pruning: если remaining < 0, отсекаем (но это сделается автоматически в цикле)


      for (let i = start; i < candidates.length; i++) {
        const num = candidates[i];


        // Pruning: если num больше remaining, все последующие тоже больше
        if (num > remaining) break;


        // Choose
        path.push(num);


        // Explore: передаём i (не i+1), так как можем использовать тот же элемент
        backtrack(i, path, remaining - num);


        // Unchoose
        path.pop();
      }
    }


    backtrack(0, [], target);
    return result;
  }


  // Permutations (LeetCode 46) — классический шаблон с used[]
  function permute(nums) {
    const result = [];
    const used = Array(nums.length).fill(false);


    function backtrack(path) {
      // Базовый случай
      if (path.length === nums.length) {
        result.push([...path]);
        return;
      }


      for (let i = 0; i < nums.length; i++) {
        if (used[i]) continue; // pruning: уже использован в текущем пути


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


        // Explore
        backtrack(path);


        // Unchoose
        path.pop();
        used[i] = false;
      }
    }


    backtrack([]);
    return result;
  }


  // N-Queens (LeetCode 51) — с битовыми масками для оптимизации
  function solveNQueens(n) {
    const result = [];
    const board = Array.from({ length: n }, () => Array(n).fill('.'));


    function backtrack(row, cols, diag1, diag2) {
      // cols, diag1, diag2 — битовые маски занятых столбцов и диагоналей
      if (row === n) {
        result.push(board.map(r => r.join('')));
        return;
      }


      for (let col = 0; col < n; col++) {
        const d1 = row - col + n - 1; // диагональ \
        const d2 = row + col;         // диагональ /


        // Проверяем атаки через битовые маски
        if ((cols & (1 << col)) || (diag1 & (1 << d1)) || (diag2 & (1 << d2))) {
          continue; // pruning
        }


        // Choose
        board[row][col] = 'Q';


        // Explore
        backtrack(
          row + 1,
          cols | (1 << col),
          diag1 | (1 << d1),
          diag2 | (1 << d2)
        );


        // Unchoose
        board[row][col] = '.';
      }
    }


    backtrack(0, 0, 0, 0);
    return result;
  }


  // Generate Parentheses (LeetCode 22) — пример pruning без явного unchoose
  function generateParenthesis(n) {
    const result = [];


    function backtrack(path, open, close) {
      // Базовый случай
      if (path.length === 2 * n) {
        result.push(path);
        return;
      }


      // Можем добавить '(', если ещё не использовали все n
      if (open < n) {
        backtrack(path + '(', open + 1, close);
      }


      // Можем добавить ')', только если ')' меньше '('
      if (close < open) {
        backtrack(path + ')', open, close + 1);
      }


      // Unchoose не нужен, так как path — строка (immutable в JS при конкатенации)
    }


    backtrack('', 0, 0);
    return result;
  }


  // Демонстрация
  console.log(combinationSum([2,3,6,7], 7)); // [[2,2,3],[7]]
  console.log(permute([1,2,3])); // [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
  console.log(solveNQueens(4)); // [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
  console.log(generateParenthesis(3)); // ["((()))","(()())","(())()","()(())","()()()"]

Трассировка

Заголовок раздела «Трассировка»

Трассировка combinationSum([2,3,6,7], 7):

  candidates = [2,3,6,7] (уже отсортированы), target = 7
  result = []


  backtrack(start=0, path=[], remaining=7):
    i=0, num=2, 2 <= 7
      path = [2]
      backtrack(0, [2], 5):
        i=0, num=2, 2 <= 5
          path = [2,2]
          backtrack(0, [2,2], 3):
            i=0, num=2, 2 <= 3
              path = [2,2,2]
              backtrack(0, [2,2,2], 1):
                i=0, num=2, 2 > 1 → break
                return
              path = [2,2] (pop)
            i=1, num=3, 3 <= 3
              path = [2,2,3]
              backtrack(1, [2,2,3], 0):
                remaining == 0 → result.push([2,2,3])
                return
              path = [2,2] (pop)
            i=2, num=6, 6 > 3 → break
            return
          path = [2] (pop)
        i=1, num=3, 3 <= 5
          path = [2,3]
          backtrack(1, [2,3], 2):
            i=1, num=3, 3 > 2 → break
            return
          path = [2] (pop)
        i=2, num=6, 6 > 5 → break
        return
      path = [] (pop)
    i=1, num=3, 3 <= 7
      path = [3]
      backtrack(1, [3], 4):
        i=1, num=3, 3 <= 4
          path = [3,3]
          backtrack(1, [3,3], 1):
            i=1, num=3, 3 > 1 → break
            return
          path = [3] (pop)
        i=2, num=6, 6 > 4 → break
        return
      path = [] (pop)
    i=2, num=6, 6 <= 7
      path = [6]
      backtrack(2, [6], 1):
        i=2, num=6, 6 > 1 → break
        return
      path = [] (pop)
    i=3, num=7, 7 <= 7
      path = [7]
      backtrack(3, [7], 0):
        remaining == 0 → result.push([7])
        return
      path = [] (pop)


  result = [[2,2,3], [7]]


  Ключевые наблюдения:
  1. Передаём start=i (не i+1) для повторного использования элемента
  2. Сортировка позволяет прервать цикл при num > remaining (pruning)
  3. Копируем path при добавлении в result: [...path]
  4. Откатываем path.pop() после каждого рекурсивного вызова

Сложность

Заголовок раздела «Сложность»

Анализ сложности: combinationSum: Time — сложно оценить точно (зависит от target и candidates), но верхняя граница O(N^(T/M)), где N = len(candidates), T = target, M = min(candidates). Интуитивно: максимальная глубина рекурсии T/M (если берём минимальный элемент), на каждом уровне до N выборов. На практике pruning сильно уменьшает количество веток. Space O(T/M) для стека рекурсии + O(result). Permutations: Time O(n · n!) — генерируем n! перестановок, каждая требует O(n) для копирования в result. Space O(n) для стека рекурсии (не считая result O(n · n!)). N-Queens: Time O(n!) факториально, но с отсечениями значительно быстрее (например, для n=8 решение за доли секунды, хотя 8! = 40320). Space O(n) для стека. Generate Parentheses: Time O(4ⁿ / √n) — n-е число Каталана Cₙ = (2n)! / ((n+1)! · n!). Space O(n) для стека.

Частые ошибки на интервью: (1) Забыть откатить изменение (path.pop, used[i]=false) — следующие ветки будут испорчены. (2) Не копировать path при добавлении в результат: result.push(path) вместо result.push([...path]) — все элементы result будут указывать на один и тот же массив, который изменяется. (3) Не проверить базовый случай первым — можем уйти в бесконечную рекурсию или обратиться к некорректному индексу. (4) Путаница в индексах: в Combinations/Subsets нужно передавать start-индекс, чтобы избежать дубликатов; в Permutations — используем массив used[], так как порядок важен. (5) В задачах с дубликатами в массиве (Combination Sum II, Subsets II) забыть отсечь дубликаты: сортируем массив, затем skip, если nums[i] == nums[i-1] && i > start.

Типичные ошибки и подводные камни

Заголовок раздела «Типичные ошибки и подводные камни»

(1) “Чем Combination Sum I отличается от II?” — В II массив может содержать дубликаты, и каждый элемент используется максимум один раз. Решение: сортируем, используем start+1 (не start), отсекаем дубликаты: if (i > start && candidates[i] == candidates[i-1]) continue;. (2) “Как оптимизировать N-Queens?” — Использовать битовые маски вместо Set/Array для проверки атак — O(1) операции вместо O(n). Диагональ ” имеет постоянное (row - col), диагональ ’/’ — (row + col). Нормализуем индексы: diag1 = row - col + n - 1 (0..2n-2), diag2 = row + col (0..2n-2). (3) “Когда переходить от backtracking к DP?” — Если подзадачи повторяются (одинаковые состояния рекурсии), добавляем мемоизацию. Пример: Word Break II (разбить строку на слова из словаря) — без мемоизации O(2ⁿ), с мемоизацией O(n² · k), где k — средняя длина слова. (4) “Palindrome Partitioning — как эффективно проверять палиндромы?” — Предварительно строим DP-таблицу isPalin[i][j] за O(n²), затем backtracking использует её за O(1). Без предрасчёта проверка палиндрома на каждом шаге даст дополнительный O(n) фактор. (5) “Subsets vs Combinations — в чём разница?” — Subsets генерирует все подмножества (2ⁿ), Combinations генерирует подмножества конкретного размера k (C(n,k) = n!/(k!(n-k)!)). Код почти одинаковый, но в Combinations добавляем условие path.length === k для базового случая.

Follow-up вопросы интервьюера

Заголовок раздела «Follow-up вопросы интервьюера»
  1. Как решить Sudoku Solver через backtracking? — Находим пустую клетку (с ’.’). Пробуем числа 1-9: если валидно (проверяем строку, столбец, блок 3×3), ставим число, рекурсивно решаем дальше. Если рекурсия вернула true → решено. Иначе откатываем (ставим ’.’) и пробуем следующее число. Если все числа не подошли → return false. Базовый случай: не осталось пустых клеток → return true. Оптимизация: предварительно для каждой клетки вычислить битовую маску доступных чисел (исключая занятые в строке/столбце/блоке), выбирать клетку с минимумом кандидатов (MRV heuristic).
  2. Word Search (LeetCode 79) — как избежать посещения одной клетки дважды? — Используем временную маркировку: при посещении клетки (r, c) меняем board[r][c] на специальный символ (например, ’#’), рекурсивно исследуем соседей, затем откатываем board[r][c] = original. Альтернатива: отдельный массив visited[r][c], но требует O(m·n) памяти. Сложность O(m·n·4ˡ), где l — длина слова, 4 — направления (с отсечениями меньше).
  3. Letter Combinations of Phone Number — оптимальная реализация? — Backtracking: на каждом уровне добавляем одну букву из текущей цифры, рекурсивно обрабатываем следующую цифру. Можно итеративно через очередь: стартуем с [""], для каждой цифры генерируем новые комбинации, добавляя каждую букву к каждой существующей комбинации. Сложность O(4ⁿ) для n цифр (7 и 9 имеют 4 буквы), но на практике O(3ⁿ · n) (большинство цифр имеют 3 буквы, и копирование строки O(n)).
  4. Combination Sum III — выбрать k чисел из 1..9, сумма = n. Как? — Backtracking: start от 1 до 9, path.length === k как условие для проверки suммы. Передаём start+1 в рекурсию (каждое число используется максимум раз). Pruning: если num > remaining, прерываем цикл. Сложность O(C(9,k)) — количество способов выбрать k из 9.
  5. Restore IP Addresses — как генерировать валидные IP? — Backtracking: разбиваем строку на 4 части, каждая длиной 1-3 символа и значением 0-255. Рекурсивно строим IP, передаём start-индекс и количество оставшихся сегментов. Базовый случай: 4 сегмента и start == s.length → добавляем в result. Pruning: (1) если сегмент начинается с ‘0’, длина должна быть 1, (2) значение должно быть <= 255, (3) если оставшихся символов больше, чем 3·segments или меньше, чем segments → отсечь (невозможно составить валидный IP).
  6. Когда использовать бэктрекинг, а когда итеративную генерацию (битовые маски)? — Битовые маски эффективны для Subsets при n <= 20 (2²⁰ = 1M): перебираем числа от 0 до 2ⁿ-1, каждый бит определяет включение элемента. Backtracking более гибок: легко добавлять условия, отсечения, работать с дубликатами. Для Permutations битовые маски неэффективны (нужен порядок, не просто включение). Для Combinations можно использовать рекурсивную формулу C(n,k) = C(n-1,k-1) + C(n-1,k), но backtracking понятнее. В общем случае backtracking — универсальнее и читабельнее, битовые маски — для специфичных задач с маленьким n.

Чеклист на собес

Заголовок раздела «Чеклист на собес»
  • Чётко выделил базовый случай и рекурсивный шаг — без базы будет stack overflow.
  • Для backtracking использую шаблон: выбор → рекурсия → откат (undo), это критично для корректности.
  • Применяю отсечения (pruning): если ветка не может дать решение — прерываю до спуска.
  • Передаю результат через аккумулятор/closure, не через возврат больших копий — экономлю память.
  • Помню про глубину рекурсии — в JS лимит ~10⁴–10⁵, при необходимости переписываю в итерацию или на стек.
  • Оцениваю сложность: backtracking обычно экспоненциальный — O(b^d) или O(n!), это нормально для перебора.
  • Знаю классические задачи: permutations, combinations, subsets, N-Queens, Sudoku, Word Search.