Рекурсия и полный перебор
Рекурсия и полный перебор: подмножества, перестановки и дерево вариантов.
Рекурсия — функция, вызывающая саму себя. У правильной рекурсии всегда два элемента: база (когда остановиться) и шаг (как свести задачу к меньшей).
Главное олимпиадное применение — полный перебор: систематически обойти ВСЕ варианты. Например, все подмножества множества: для каждого элемента два выбора — взять или не взять. Получается дерево вариантов глубины n с 2ⁿ листьями.
Все подмножества. Введите: 3, затем 1 2 3
Строка current.pop_back() — сердце приёма под названием backtracking (перебор с откатом): сделали выбор, исследовали ветку, ОТМЕНИЛИ выбор и пробуем следующий. Забытая отмена — ошибка номер один в переборах.
Оцените масштабы: 2ⁿ подмножеств — перебор реален при n до ~20-25. Перестановок ещё больше: n! (при n = 10 уже 3.6 миллиона). Для перестановок в C++ есть готовый next_permutation.
Все перестановки строки. Введите: abc
Когда полный перебор слишком велик, спасают отсечения: не заходить в ветку, которая заведомо не даст ответа. Умный перебор с отсечениями решает задачи, где «в лоб» — вечность.
Задание: выведите все способы расставить знаки + и - между числами 1 2 3 4 так, чтобы результат равнялся нулю (перебор 2³ вариантов знаков).
Отметьте урок пройденным и переходите к жадным алгоритмам.