re:re:actable
Урок 083 минуты чтения

Что такое backtracking?

На этой странице
Кратко

Backtracking - паттерн полного перебора с откатом выбора. Он используется для permutations, combinations, subsets, задач с доской, скобками и поиском всех вариантов.

Вопрос

Что такое backtracking и как строить перебор с откатом?

Идея

choose -> explore -> undo

Мы строим частичное решение, рекурсивно продолжаем, а затем откатываем выбор.

Subsets

function subsets(nums: number[]): number[][] {
  const result: number[][] = []
  const path: number[] = []
 
  function dfs(index: number): void {
    if (index === nums.length) {
      result.push([...path])
      return
    }
 
    path.push(nums[index])
    dfs(index + 1)
    path.pop()
 
    dfs(index + 1)
  }
 
  dfs(0)
  return result
}

Для каждого элемента два выбора: взять или не взять. Для nums = [1, 2] дерево решений выглядит так:

                    []
           взять 1 /  \ не брать 1
                [1]    []
       взять 2 /  \    /  \
           [1,2]  [1] [2]  []

Листья дерева - все 4 подмножества. path.pop() - это и есть "откат": вернулись из левой ветки и пробуем правую с тем же состоянием, что было до выбора.

Сложность:

Time: O(n * 2^n) - 2^n подмножеств, каждое копируется за O(n)
Space: O(n) без учета output - глубина рекурсии и path

Permutations

function permutations(nums: number[]): number[][] {
  const result: number[][] = []
  const path: number[] = []
  const used = new Set<number>()
 
  function dfs(): void {
    if (path.length === nums.length) {
      result.push([...path])
      return
    }
 
    for (let i = 0; i < nums.length; i++) {
      if (used.has(i)) continue
 
      used.add(i)
      path.push(nums[i])
      dfs()
      path.pop()
      used.delete(i)
    }
  }
 
  dfs()
  return result
}

Перестановок n!, каждую копируем за O(n), поэтому time O(n * n!).

Pruning - отсечение веток

Backtracking становится быстрее, если не заходить в ветки, которые точно не дадут ответ. Пример: найти все наборы из candidates с суммой target, каждое число можно брать много раз.

function combinationSum(candidates: number[], target: number): number[][] {
  const sorted = [...candidates].sort((a, b) => a - b)
  const result: number[][] = []
  const path: number[] = []
 
  function dfs(start: number, remaining: number): void {
    if (remaining === 0) {
      result.push([...path])
      return
    }
 
    for (let i = start; i < sorted.length; i++) {
      if (sorted[i] > remaining) break // pruning: дальше числа только больше
 
      path.push(sorted[i])
      dfs(i, remaining - sorted[i])
      path.pop()
    }
  }
 
  dfs(0, target)
  return result
}
 
combinationSum([2, 3, 6, 7], 7) // [[2, 2, 3], [7]]

Без break мы бы продолжали перебирать заведомо слишком большие числа. start не дает получить одни и те же наборы в разном порядке ([2, 2, 3] и [3, 2, 2]).

Что отвечать на собеседовании?

Backtracking - это DFS по дереву решений. На каждом шаге мы делаем выбор, рекурсивно исследуем последствия и откатываем выбор. Он подходит для задач, где нужно найти все комбинации, перестановки или валидные конфигурации. Сложность часто экспоненциальная, потому что мы перебираем пространство вариантов.

Что важно помнить: частые ошибки

  • Не делать копию path при добавлении в result.
  • Забывать pop/undo.
  • Не ставить base case.
  • Не использовать pruning.
  • Не учитывать экспоненциальную сложность.

Мини-шпаргалка

  • Choose.
  • Explore.
  • Undo.
  • DFS по решениям.
  • path хранит текущий вариант.
  • result.push([...path]), не path.
  • Часто O(2^n) или O(n!).

Документация

Wikipedia: Backtracking.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам