Что такое 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 - глубина рекурсии и pathPermutations
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!).