Рекурсия и перебор с возвратом

Перед началом: рекурсия в стеке и обходах (модули 5, 6, 11 — достаточно интуиции вызовов). Инструменты: Go 1.27, slices, sort. Трудоёмкость: ~5 ч (теория 2 ч · практика 3 ч).

🔥 Инцидент: «Генератор расписаний повесил очередь воркеров»

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

Спасение — перебор с возвратом (backtracking) с отсечениями: строим решение по шагу и откатываемся сразу, как только очередной выбор уже противоречит ограничениям. Число листьев дерева падает с 3ⁿ до практически разумного. В модуле — шаблон перебора, подмножества, перестановки, комбинации с суммой и отсечения на примере N-ферзей.

📖 Теория

7.1 Рекурсия: база, шаг и глубина

Рекурсивная функция состоит из базы (когда отвечаем сразу) и шага (задача меньше). Две вещи, которые в Go надо помнить:

• хвостовой рекурсии в Go нет — компилятор не превращает её в цикл, каждый вызов занимает кадр стека;
• бесконечная рекурсия — это паника, а не вежливая ошибка: fatal error: stack overflow кладёт весь процесс.

Поэтому правило простое: если глубина может быть произвольной (обход сотни тысяч узлов — инцидент модуля 11), рекурсию заменяют циклом со стеком. Если глубина ограничена постановкой (перестановки длины ≤ 10, доска ферзей ≤ 12), рекурсия — самый читаемый инструмент.

7.2 Шаблон choose — explore — unchoose

Перебор с возвратом — это DFS по дереву решений (модуль 14, но здесь граф — «варианты выбора»). Шаблон из трёх шагов:

go
func backtrack(state *state, path []int, out *[][]int) {
	if done(state) { // 1) решение готово — сохранить копию
		*out = append(*out, append([]int(nil), path...))
		return
	}
	for _, choice := range options(state) {
		if !feasible(state, choice) {
			continue // 2) отсечение: ветку не развиваем
		}
		apply(state, choice)   // 3) choose
		backtrack(state, append(path, choice), out) // explore
		undo(state, choice)    // unchoose: состояние вернулось как было
	}
}

Два invariant, которые ломаются чаще всего:

• копия ответа: append([]int(nil), path...) — если положить сам path, все ответы в out будут ссылаться на один изменяемый срез;
• полный откат: после explore состояние обязано вернуться ровно в то, каким было до choose — иначе «призраки» решений протекут в соседние ветки.

7.3 Подмножества и перестановки

Подмножества (power set): для каждого элемента — два выбора, «взять» или «не взять».

go
func subsets(a []int) [][]int {
	var out [][]int
	var walk func(i int, path []int)
	walk = func(i int, path []int) {
		if i == len(a) {
			out = append(out, append([]int(nil), path...))
			return
		}
		walk(i+1, path)             // не берём a[i]
		walk(i+1, append(path, a[i])) // берём a[i]
	}
	walk(0, nil)
	return out
}

Порядок важен: сначала «без», потом «с» — классический лексикографический вывод. Перестановки — тот же шаблон, но состоянием становится массив использованных used[]:

go
// used[i] помечает занятые позиции; дубликаты отсекаются сортировкой:
// если a[i] == a[i-1] и a[i-1] не использован — эта ветка уже была.

Отсечение дубликатов — типичный вопрос собеседования: без сортировки и проверки used[i-1] перестановки с повторами выходят многократно.

7.4 Комбинации с суммой: включение и отсечение

Задача «все комбинации кандидатов с суммой target» собирается из двух идей: перебор без повторного использования (индекс start — растим только вправо) и отсечение по перебору суммы (если сортировать кандидатов, то при sum > target можно оборвать цикл, а не проверять остаток):

go
func combinationSum(cands []int, target int) [][]int {
	sort.Ints(cands) // сортировка даёт отсечение: дальше числа только больше
	var out [][]int
	var walk func(start, sum int, path []int)
	walk = func(start, sum int, path []int) {
		if sum == target {
			out = append(out, append([]int(nil), path...))
			return
		}
		for i := start; i < len(cands); i++ {
			if sum+cands[i] > target {
				break // отсечение: все дальнейшие кандидаты ещё больше
			}
			walk(i, sum+cands[i], append(path, cands[i]))
		}
	}
	walk(0, 0, nil)
	return out
}

Заметьте: walk(i, ...) — не walk(i+1, ...): i-й кандидат можно брать многократно; для варианта «каждый не более раза» шаг меняется на i+1.

7.5 Отсечения: N-ферзей

Классика отсечений: расставить N ферзей на доске N×N так, чтобы они не били друг друга. Перебор по столбцам + три проверки на конфликт — диагонали проверяются множествами diag1[row+col], diag2[row-col], без повторного сканирования доски:

go
func solveQueens(n int) (solutions, nodes int) {
	cols := make([]bool, n)
	d1 := make([]bool, 2*n)   // диагонали «сверху-слева вниз-вправо»
	d2 := make([]bool, 2*n)   // диагонали «сверху-справа вниз-влево»
	var place func(row int)
	place = func(row int) {
		nodes++
		if row == n {
			solutions++
			return
		}
		for col := 0; col < n; col++ {
			if cols[col] || d1[row+col] || d2[row-col+n-1] {
				continue // отсечение: клетка под боем
			}
			cols[col], d1[row+col], d2[row-col+n-1] = true, true, true
			place(row + 1)
			cols[col], d1[row+col], d2[row-col+n-1] = false, false, false
		}
	}
	place(0)
	return solutions, nodes
}

Счётчик nodes — это и есть цена перебора: сравните его с n! (полный перебор перестановок ферзей по столбцам) — отсечения убирают почти всё.

7.6 Компромиссы

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

💻 Практика

1. Подмножества двумя способами. Рекурсией из §7.3 и битовыми масками (модуль 19 — забегая вперёд, for mask := 0; mask < 1<<n; mask++). Сравните число ветвлений и проверьте одинаковый набор ответов.
2. Перестановки с дубликатами. permuteUnique([1, 1, 2]) должен дать три уникальные перестановки, а не шесть. Решите с сортировкой и used[], объясните в комментарии, почему проверки used[i-1] вместе с сортировкой хватает.
3. Комбинации с суммой. Два варианта: кандидат можно использовать многократно и каждое число не более раза. Тесты: target меньше минимального кандидата, единственная комбинация, пустой ответ.
4. Скобки. Сгенерировать все правильные последовательности из n пар скобок (для n = 3 — пять штук). Отсечение «закрывающая только при открывающих в запасе» держит дерево маленьким — докажите это числом узлов.
5. N-ферзей со счётчиками. Проверьте для n = 4 (2 решения), n = 6 (4), n = 8 (92). Добавьте счётчик посещённых узлов и сравните с полным перебором перестановок (n!): во сколько раз отсечения сжали дерево.

🧩 Quiz

✅ Итоги модуля

• Перебор с возвратом — DFS по дереву решений: шаблон choose — explore — unchoose, копия ответа и полный откат — два самых частых источника багов.
• Подмножества: два выбора на элемент; перестановки: used[] плюс сортировка для дедупликации.
• Комбинации с суммой: start-индекс, сортировка и break при превышении — отсечение вместо проверки.
• Отсечения превращают экспоненту в практичную величину: диагональные множества N-ферзей считают узлы вместо полного n!.
• Если нужен один оптимум, а не все варианты, — это DP, а не бэктрекинг.

🔗 Мостик к Модулю 8

Перебор с отсечениями опирался на сортировку кандидатов — и мы принимали её как услугу стандартной библиотеки. Пора разобрать, откуда она берётся. В модуле 8 — «Сортировки: от insertion sort до quick sort»: квадратичные сортировки и их единственное правильное применение, merge и quick изнутри с partition, стабильность сортировки — и что на самом деле вызывает slices.Sort.