Алгоритмы с нуля
Подмножества и перестановки
Ты уже знаешь шаблон backtracking: выбрать, исследовать, отменить. С ним открываются две задачи: сгенерировать каждое подмножество набора из n элементов и сгенерировать каждое упорядочение (перестановку) этих элементов. Это “Hello World” backtracking’а — не потому что просто, а потому что это самые ясные примеры шаблона в действии. В подмножествах ты ветвишься на включить/исключить. В перестановках ты ветвишься на какой неиспользованный элемент идёт дальше. Обе задачи бьют во все выходы; их быстрее ты не сделаешь. Зато можешь сделать ясными.
После этого урока ты можешь написать функцию backtracking’а для генерирования всех подмножеств набора (степенного множества) и всех перестановок списка. Ты понимаешь, почему есть 2ⁿ подмножеств и n! перестановок — потому что сам вывод такой большой. Ты видишь, что обе задачи применяют один и тот же шаблон выбрать-исследовать-отменить с разной логикой “выбора” на каждом шаге.
Подмножества: степенное множество
Подмножество — это любой выбор элементов из набора. Степенное множество — это набор всех подмножеств.
Пример: для набора {1, 2, 3}, степенное множество это:
{}(пусто){1},{2},{3}(одиночные){1, 2},{1, 3},{2, 3}(пары){1, 2, 3}(все)
Итого: 8 подмножеств = 2³.
Почему 2ⁿ? Каждый элемент имеет ровно 2 выбора: включить его или исключить. С n независимыми бинарными выборами есть 2ⁿ исходов.
Форма backtracking’а для подмножеств
На каждом шаге решай: включить текущий элемент или исключить его. Это выбор. Рекурсируй для каждого варианта.
function subsets(arr, index, current, result):
if index == len(arr):
result.append(copy(current))
return
# Выбор 1: Включить arr[index]
current.push(arr[index])
subsets(arr, index + 1, current, result)
current.pop()
# Выбор 2: Исключить arr[index]
subsets(arr, index + 1, current, result)На каждом уровне дерево ветвится на два: один где элемент в подмножестве, один где его нет. Глубина — n (один уровень на элемент). На дне у тебя 2ⁿ листьев (подмножеств).
Перестановки: все упорядочения
Перестановка — это упорядочение n элементов. Для набора из n отличных элементов есть n! перестановок.
Пример: {1, 2, 3} имеет 3! = 6 перестановок: 123, 132, 213, 231, 312, 321.
Почему n!? На позиции 0 у тебя есть n выборов какой элемент идёт первым. На позиции 1 у тебя есть n-1 оставшихся выборов. На позиции 2 есть n-2 выбора. И так далее: n × (n-1) × (n-2) × … × 1 = n!.
Форма backtracking’а для перестановок
На каждом шаге решай: какой неиспользованный элемент идёт дальше? Отметь его использованным, рекурсируй, потом отметь обратно (отмени).
function permutations(arr, used, current, result):
if len(current) == len(arr):
result.append(copy(current))
return
for i in range(len(arr)):
if not used[i]:
# Выбор: поставить arr[i] в эту позицию
used[i] = True
current.push(arr[i])
permutations(arr, used, current, result)
current.pop()
used[i] = False # ОтмениНа каждом уровне у тебя есть n, потом n-1, потом n-2, … выборов. На дне у тебя есть n! листьев (перестановок).
Один и тот же шаблон, разные выборы
Обе задачи используют паттерн выбрать-исследовать-отменить. Для подмножеств выбор бинарный: включить или исключить. Для перестановок выбор n-арный (или меньше когда ты сужаешь неиспользованный набор): какой элемент идёт дальше. Одна и та же структура, разная логика.
Ты не можешь биться размером вывода
Оба 2ⁿ и n! — это размер ВЫВОДА — количество отличных подмножеств и перестановок. Ты не можешь сгенерировать меньше без пропусков. Так что лучшее что ты можешь сделать это O(n × 2ⁿ) для подмножеств (n время на построение каждого) и O(n × n!) для перестановок (n время на построение каждого). Ты генерируешь все ответы; ты не можешь лучше чем размер ответа раз на работу на запись каждого.
Давай кодим обе: генерируй все подмножества и все перестановки.
Пример 1: Сгенерируй все подмножества
function allSubsets(arr) {
const result = [];
function backtrack(index, current) {
// Базовый случай: изучили все элементы
if (index === arr.length) {
result.push([...current]); // Запиши подмножество
return;
}
// Выбор 1: Включить arr[index]
current.push(arr[index]);
backtrack(index + 1, current);
current.pop(); // Отмени
// Выбор 2: Исключить arr[index]
backtrack(index + 1, current);
}
backtrack(0, []);
return result;
}
console.log(allSubsets([1, 2, 3]));
// Вывод: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]Пример 2: Сгенерируй все перестановки
function allPermutations(arr) {
const result = [];
const used = new Array(arr.length).fill(false);
function backtrack(current) {
// Базовый случай: построили полную перестановку
if (current.length === arr.length) {
result.push([...current]);
return;
}
// Попробуй каждый неиспользованный элемент в этой позиции
for (let i = 0; i < arr.length; i++) {
if (!used[i]) {
// Выбор: поставить arr[i] сюда
used[i] = true;
current.push(arr[i]);
backtrack(current);
current.pop(); // Отмени
used[i] = false;
}
}
}
backtrack([]);
return result;
}
console.log(allPermutations([1, 2, 3]));
// Вывод: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]Попробуй обе:
Давай проследим генерирование всех подмножеств [1, 2] чтобы увидеть паттерн выбрать-исследовать-отменить.
1
function allSubsets(arr) {
2
function backtrack(index, current) {
3
if (index === arr.length) {
4
result.push([...current]); return;
5
}
6
current.push(arr[index]);
7
backtrack(index + 1, current);
8
current.pop();
9
backtrack(index + 1, current);
10
}
11
}
Паттерн: на каждом элементе раздвойся на два пути (включить или исключить), иди глубоко, вернись, исследуй другой путь. Все 2ⁿ подмножеств посетины ровно один раз.
Подмножества: Время O(n × 2ⁿ), Пространство O(n)
- Дерево рекурсии имеет глубину n (один уровень на элемент).
- На каждом уровне ты ветвишься на 2 пути (включить или исключить). Так что дерево имеет 2ⁿ листьев.
- Каждый лист — это полное подмножество. Построить каждое подмножество берёт O(n) времени (копирование n элементов).
- Время = 2ⁿ подмножеств × O(n) времени на подмножество = O(n × 2ⁿ).
- Пространство (стек вызовов) = O(n) (глубина рекурсии).
- Ты не можешь лучше: сам вывод это 2ⁿ подмножеств, так что ты должен потратить минимум O(2ⁿ) времени на запись их.
Перестановки: Время O(n × n!), Пространство O(n)
- Дерево рекурсии имеет глубину n (одна позиция на элемент).
- На уровне 0 у тебя есть n выборов (какой элемент идёт первым). На уровне 1 у тебя есть n-1 оставшихся выборов. На уровне 2 у тебя есть n-2 выбора. И так далее.
- Общее количество листьев = n × (n-1) × (n-2) × … × 1 = n!.
- Каждый лист — это полная перестановка. Построить каждую берёт O(n) времени (копирование n элементов).
- Время = n! перестановок × O(n) времени на перестановку = O(n × n!).
- Пространство (стек вызовов) = O(n) (глубина рекурсии).
- Ты не можешь лучше: сам вывод это n! перестановок, так что ты должен потратить минимум O(n!) времени.
Почему выводы экспоненциальные/факториальные
Это по природе большое. С n элементами:
- Подмножества: 2ⁿ растёт экспоненциально. Для n=20, это около ~1 миллиона подмножеств.
- Перестановки: n! растёт факториально, ещё быстрее. Для n=10, это 3,6 миллиона перестановок. Для n=12, это 479 миллионов.
Ты не можешь биться размером вывода. Алгоритм оптимален: он трогает каждый вывод один раз.
Сколько подмножеств имеет набор из 4 элементов?
Сколько перестановок [1, 2, 3, 4] есть?
Какова ключевая разница между генерированием подмножеств и генерированием перестановок?
Сколько раз базовый случай выполняется при генерировании всех подмножеств массива из 3 элементов?
Для перестановок из n элементов, почему временная сложность O(n × n!) а не просто O(n!)?
Частая ошибка
Ошибка: забыть отменить флаг использования (или не скопировать подмножество). Ты генерируешь все перестановки. Когда ты отмечаешь used[i] = true и рекурсируешь, ты должен установить used[i] = false когда ты отступаешь. Иначе элемент остаётся отмеченным и позже перестановки не могут его использовать.
Аналогично, когда ты собираешь подмножество, ты должен его скопировать ([...current] или list(current)), не просто добавить ссылку. Иначе все твои подмножества указывают на один массив, и когда ты удаляешь элемент, все подмножества его теряют.
// НЕПРАВИЛЬНО (перестановки)
for (let i = 0; i < arr.length; i++) {
if (!used[i]) {
used[i] = true;
current.push(arr[i]);
backtrack(current);
current.pop();
// ОШИБКА: забыл used[i] = false!
}
}
// ПРАВИЛЬНО
for (let i = 0; i < arr.length; i++) {
if (!used[i]) {
used[i] = true;
current.push(arr[i]);
backtrack(current);
current.pop();
used[i] = false; // Отмени отметку
}
}
// НЕПРАВИЛЬНО (подмножества)
if (index === arr.length) {
result.push(current); // ОШИБКА: одна ссылка!
return;
}
// ПРАВИЛЬНО
if (index === arr.length) {
result.push([...current]); // Скопируй массив
return;
}Отмена и копирование не опциональны. Без них все твои выводы коллапсируют в один.
Ты генерируешь все подмножества массива размера 5. Сколько их есть и какова временная сложность для генерирования их всех?
Подмножества: Генерируй все возможные выборы набора. Для набора из n элементов, есть 2ⁿ подмножеств (степенное множество). На каждом элементе выбери включить или исключить. Глубина дерева = n, ветвление = 2 на узел, листья = 2ⁿ.
Перестановки: Генерируй все упорядочения n элементов. Есть n! перестановок. На каждой позиции выбери какой неиспользованный элемент идёт дальше. Глубина дерева = n, ветвление = n, n-1, n-2, … на уровне, листья = n!.
Один и тот же шаблон, разные выборы: Обе используют паттерн выбрать-исследовать-отменить. Логика выбора отличается (включить/исключить против какого элемента), но структура идентична.
Сложность: Подмножества это O(n × 2ⁿ) времени и O(n) пространства. Перестановки это O(n × n!) времени и O(n) пространства. Ты не можешь лучше: размер вывода это 2ⁿ или n!, и ты должен трогать каждый вывод.
Почему они экспоненциальные/факториальные: Сам вывод того размера. С n элементами, есть по природе 2ⁿ способов включить/исключить, и n! упорядочений. Это считает; алгоритм оптимален — он совпадает с размером вывода.