Рекурсия и перебор с отсечениями: шаблоны и переход к DP ТЕМА

О чём статья

Рекурсия — самая универсальная техника алгоритмики: ей решается любая задача, где ответ для целого определяется ответом для меньших частей. Цена универсальности — без аккуратной работы со структурой перебора экспоненциальная сложность убивает любую попытку уложиться в TL. Поэтому в реальной тренировке «знание рекурсии» означает не один навык, а четыре последовательных уровня: написать чистую рекурсию по дереву решений, добавить отсечения там, где это не ломает корректность, заменить повторяющиеся вызовы мемоизацией, и — где это даёт стабильный выигрыш — перевести то же самое в итеративный DP.

Эта статья — про каркас, по которому шагают все четыре уровня. Цель — чтобы при виде задачи с маленькими ограничениями вида $n \le 20$, $n \le 40$ или «перечислить все способы», рука сразу тянулась за рекурсивным каркасом, а в случае повторных подзадач — за мемоизацией. И чтобы переход от рекурсии к DP не выглядел как «другой алгоритм», а воспринимался как та же формула, аккуратно записанная без вызова функции.

---

Когда применять: сигналы в условии

• «Перечислить все», «сколько способов», «существует ли набор». Прямой сигнал на перебор. Если ответ — структурный объект (подмножество, перестановка, разбиение), почти всегда стартуем с рекурсии.
• Маленькое ограничение по «структурной» оси. $n \le 20$ намекает на $2^n$ — перебор подмножеств. $n \le 10$ — перестановки или вложенный перебор. $n \le 40$ — meet-in-the-middle, всё ещё рекурсия в основе.
• «Сумма / произведение / комбинация» с малым диапазоном. $\text{sum} \le 10^4$, $K \le 100$ — сигнал, что состояние можно явно описать и закэшировать; рекурсия плавно превращается в DP.
• Условие даёт древовидную структуру выбора. «На шаге $i$ можно либо $X$, либо $Y$» — естественное дерево решений. Если дерево «глубокое и узкое» (фиксированная глубина $n$, на каждом уровне 2–3 варианта) — почти всегда работает $O(2^n)$ или мемоизация.
• «Найти лексикографически минимальное», «вывести сам набор». Перебор удобен тем, что попутно строит сам объект; DP-таблица хранит только число, и для восстановления нужен отдельный проход.

Если сигналов нет — рекурсия, скорее всего, не нужна. Если ограничения большие ($n \ge 10^5$), а перебор пишется на $2^n$ — это явный признак, что задача требует не перебора, а структурного приёма (жадный, DP по другому индексу, графовый алгоритм).

---

Базовый шаблон

Идея в одну фразу

Перебор устроен как обход дерева решений в глубину: на каждом шаге фиксируем один выбор, рекурсивно решаем подзадачу для оставшихся шагов, возвращаемся и пробуем следующий вариант.

Псевдокод чистой рекурсии

функция solve(state):
    если состояние терминальное:
        обновить ответ или вернуть значение
        return
    для каждого допустимого варианта v на шаге state:
        применить v к state    // войти в выбор
        solve(state')
        откатить v из state    // выйти из выбора

Базовая идея: состояние — это набор уже сделанных выборов, варианты — что можно сделать на следующем шаге. Возврат из solve гарантирует, что мы попробовали поддерево; откат необходим, потому что одни и те же структуры (массив, флажки) переиспользуются для соседних веток.

Базовый шаблон с отсечениями

функция solve(state, current_value):
    если состояние терминальное:
        обновить ответ
        return
    если current_value уже хуже лучшего ответа:   // отсечение по оценке
        return
    если нарушен инвариант:                       // отсечение по инварианту
        return
    для каждого допустимого варианта v (в правильном порядке):
        применить v
        solve(state', current_value + delta)
        откатить v

Отсечения — два класса:

• По оценке. Если уже текущий промежуточный результат хуже зафиксированного лучшего, дальше делать нечего. Лучший результат держим в нелокальной переменной (глобальной или ссылке).
• По симметрии / инварианту. Если выбор приводит к структурно эквивалентному поддереву (например, переставленные индексы), пропускаем. Самый известный пример — N-queens, где можно требовать упорядоченности по строкам.

Базовый шаблон с мемоизацией

cache ← пустая таблица
функция solve(state):
    если state в cache:
        вернуть cache[state]
    если состояние терминальное:
        вернуть базовый ответ
    результат ← агрегация по вариантам:
        для каждого допустимого варианта v:
            agg(результат, f(v, solve(state')))
    cache[state] ← результат
    вернуть результат

Главное отличие от перебора: функция возвращает значение, а не обновляет глобальный счётчик. Это требование мемоизации — кэш связывает состояние с ответом, а не с побочным эффектом. Если структура «вернуть значение» не получается естественно, мемоизация не подойдёт.

Почему работает

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

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

---

Задача-иллюстрация 1: подсчёт подмножеств с заданной суммой (~CF 1300)

Условие

Дан массив из $n$ положительных целых чисел $a_1, \ldots, a_n$ и целое число $K$. Нужно найти количество подмножеств массива, сумма элементов которых равна ровно $K$. Подмножество идентифицируется множеством индексов, поэтому одинаковые значения на разных позициях считаются разными.

Ограничения. $1 \le n \le 30$, $1 \le a_i \le 10^9$, $1 \le K \le 10^{18}$.

Пример. $n = 4$, $a = [1, 2, 3, 4]$, $K = 5$. Ответ — $2$: подмножества $\{1, 4\}$ и $\{2, 3\}$.

Применение шаблона

Состояние — позиция $i$ (сколько элементов уже рассмотрено) и текущая сумма $s$. На шаге $i$ два варианта: «взять $a_i$» (перейти к $(i + 1, s + a_i)$) или «не взять» (перейти к $(i + 1, s)$). Терминальное состояние — $i = n$, тогда возвращаем $1$, если $s = K$, и $0$ иначе.

Это чистый перебор без отсечений. Сложность — $O(2^n)$. При $n = 30$ — около $10^9$, на грани TL. Можно ускорить отсечением: если $s$ уже превысила $K$, останавливаем ветку — дальше элементы только увеличивают сумму (по условию положительные).

С мемоизацией здесь сложно работать «в лоб»: $s$ может быть до $10^{18}$, кэш по состоянию $(i, s)$ не помещается. Если бы $K$ было маленьким ($\le 10^4$), кэш по $(i, s)$ дал бы $O(n \cdot K)$ — это и есть классический «subset sum DP».

Разбор на примере

$a = [1, 2, 3, 4]$, $K = 5$. Дерево решений:

                      (0, 0)
              взять 1 /        \ не взять
                    (1,1)        (1,0)
            взять 2 /  \ не взять  ...
                  (2,3)  (2,1)
        взять 3 /   \ не взять
              (3,6)*    (3,3)
                      взять 4 / \ не взять
                          (4,7)*  (4,3)  ← не 5, отбрасываем

Звёздочкой помечены случаи, где сумма превысила $K = 5$ (отсечение по оценке). Лист $(4, 5)$ встречается на двух разных путях: $1 + 4$ и $2 + 3$. Ответ — $2$.

Код решения

Глубина рекурсии в Python: при $n = 30$ это безопасно даже без setrecursionlimit. Для перестраховки выставили 100. На больших $n$ (до 40 и выше с meet-in-the-middle) можно столкнуться с переполнением стека — тогда либо setrecursionlimit(10000), либо переписывать итеративно через bitmask.

Что поменялось

Чистый перебор + одно отсечение по оценке. Это минимальный шаг от классической рекурсии, который уже даёт ускорение на тестах, где целевое $K$ маленькое относительно суммы массива. На пограничных тестах ($n = 30$, $K$ близко к полусумме) отсечение почти ничего не даёт — там нужно meet-in-the-middle (разделить массив на две половины по 15 элементов, перебрать все подсуммы каждой половины и соединить через хешмап). Это уже не базовая рекурсия, а её комбинация со структурой данных.

---

Задача-иллюстрация 2: подсчёт способов разменять сумму монетами (~CF 1500)

Условие

Дано $n$ номиналов монет $c_1, c_2, \ldots, c_n$ и сумма $S$. Каждая монета доступна в неограниченном количестве. Найти количество способов набрать сумму $S$ из этих монет, где порядок монет не важен (т.е. набор $\{c_1, c_1, c_2\}$ и $\{c_1, c_2, c_1\}$ — один и тот же способ).

Ограничения. $1 \le n \le 100$, $1 \le c_i \le 100$, $1 \le S \le 10^4$.

Пример. Номиналы $[1, 2, 3]$, $S = 4$. Ответ — $4$: $4 = 1+1+1+1 = 1+1+2 = 2+2 = 1+3$.

Применение шаблона

Состояние — пара $(i, s)$: рассмотрены номиналы $1..i$, набрана сумма $s$. На шаге $i$ перебираем, сколько монет $i$-го номинала взяли — $k = 0, 1, 2, \ldots$, пока $k \cdot c_i \le S - s$. Переходим в $(i + 1, s + k \cdot c_i)$.

Терминальное состояние: $i = n$. Возвращаем $1$, если $s = S$, и $0$ иначе. Чистый перебор даёт экспоненциальную сложность — на тестах $n = 100$, $S = 10^4$ не пройдёт.

Но! Состояние $(i, s)$ полностью описывает оставшуюся задачу. Состояний всего $O(n \cdot S) = 10^6$. Это сигнал к мемоизации.

Как пишется мемоизация

После того как чистая рекурсия написана, добавляем кэш по (i, s). Если функция вернула значение для этого состояния раньше — отдаём из кэша. Иначе считаем и кладём в кэш.

После добавления кэша сложность падает с $O(2^{O(S/c_{\min})})$ до $O(n \cdot S \cdot S / c_{\min})$ — последний множитель из-за того, что переход по $k$ занимает до $S / c_i$ шагов. На $n = 100$, $S = 10^4$, $c_{\min} = 1$ — это $10^{10}$, всё ещё много.

Чтобы убрать лишний фактор, перебор по $k$ заменяется на «либо взять одну монету $i$ и остаться на шаге $i$ (разрешая взять ещё), либо перейти к $i + 1$». Это даёт сложность $O(n \cdot S)$ — стандартная DP по монетам.

Разбор на примере

$c = [1, 2, 3]$, $S = 4$. Считаем $f(i, s)$ — число способов набрать $s$ монетами номиналов $i..n - 1$. Базовый случай: $f(n, 0) = 1$; $f(n, s) = 0$ при $s \ne 0$.

Ответ — $f(0, 4) = 4$. Сходится с ручным разбором.

Код решения

Что поменялось

Главное усложнение — функция возвращает значение, а не обновляет нелокальный счётчик. Это требование мемоизации. Если попытаться кэшировать функцию, которая обновляет глобальный ans, кэш не работает: «вернули из кэша» не равно «прибавили к счётчику».

Второе — переход от перебора $k$ к двум вариантам «взять ещё один $c_i$» / «перейти к $i + 1$». Этот трюк удваивает число вершин в дереве рекурсии, но убирает лишний фактор $S / c_i$ из каждого перехода. На итоговую сложность с мемоизацией это влияет драматически: $O(n \cdot S)$ вместо $O(n \cdot S^2 / c_{\min})$.

Переход к итеративному DP

Мемоизированная рекурсия и итеративный DP — это одна и та же формула, записанная двумя способами. У нас была формула $f(i, s) = f(i, s - c_i) + f(i + 1, s)$. Запишем её итеративно, в направлении от больших $i$ к меньшим, для каждого $s$ от $0$ до $S$:

dp[n+1][S+1] = 0
dp[n][0] = 1
для i от n - 1 до 0:
    для s от 0 до S:
        dp[i][s] = dp[i+1][s]                           // не берём i
        если s - c[i] ≥ 0:
            dp[i][s] += dp[i][s - c[i]]                 // берём ещё один c[i]
ответ = dp[0][S]

Эта версия:

• не требует кэша (хранение — двумерный массив или одномерный rolling, размер $O(S)$);
• избегает накладных расходов на вызовы функции (особенно важно в Python — заметное ускорение);
• не требует увеличения setrecursionlimit.

Минус — менее «понятный» вид: не видно дерева рекурсии, и легче ошибиться с порядком обхода. На олимпиаде выбор между мемоизацией и итеративным DP — вопрос привычки и характера задачи. Для задач с порядок-зависимым состоянием (например, DP на дереве, на интервалах) мемоизация часто проще; для классического «по индексам» — итеративный DP надёжнее.

---

Типичные ошибки

1. Забытый откат изменения в backtracking. Если на шаге «взять» меняли разделяемую структуру (массив used[], текущую сумму на ссылке), а на возврате не восстановили — следующая ветка увидит «грязное» состояние. Симптом: правильный ответ на маленьких тестах, мусор на больших.
2. Мемоизация с побочными эффектами. Кэшировать функцию, которая обновляет глобальный счётчик или печатает что-то, нельзя. Кэш ловит только возврат, побочные эффекты не воспроизводятся. Если функция нужна для побочных эффектов — мемоизация не для неё.
3. Состояние не описывает оставшуюся задачу. Если ответ функции зависит не только от аргументов, но и от того, как мы туда пришли (например, от множества посещённых вершин, не входящего в state), мемоизация даст неверный результат. Симптом: при чистой рекурсии всё хорошо, после добавления кэша — WA.
4. Отсечение убивает корректное поддерево. Отсечение по оценке корректно только если оценка — гарантированная граница (нижняя для максимизации, верхняя для минимизации). Жадная оценка («скорее всего, не лучше») — некорректное отсечение.
5. Переполнение при больших значениях суммы. В задаче 1 сумма может достигать $30 \cdot 10^9 = 3 \cdot 10^{10}$. В C++ — обязательно long long. В Python — нет проблем.
6. Глубина рекурсии в Python. При $n \le 20$–$30$ всё в порядке. При $n \ge 1000$ — обязательный sys.setrecursionlimit(...). На очень больших — итеративная переписка (стек руками или DP).
7. Использование dict вместо dp[i][s] в C++. На больших таблицах unordered_map<pair<int,int>, ...> медленнее в 5–10 раз, чем vector<vector<long long>>. Если состояние плотное по ключу — массив всегда быстрее.
8. Кэш сбрасывается между тестами. В задачах с несколькими тест-кейсами в одном запуске — cache.clear() в начале каждого теста. Иначе соседние тесты «загрязняют» друг друга.

---

Когда НЕ подходит

• Большое $n$ при экспоненциальной структуре. $n = 100$ и нужно перебрать подмножества — рекурсия не поможет. Нужна другая идея (DP по подмножествам не помещается тоже; иногда — meet-in-the-middle, иногда — структурное наблюдение).
• Состояние не описывается компактно. Если для оценки «эквивалентны ли два пути» нужно сравнить два массива длины $n$ — мемоизация не работает. Кэш по такому ключу будет линейного размера на каждый вызов, и выигрыша нет.
• Глубокое-узкое дерево с большой стоимостью одного шага. Если каждый рекурсивный шаг — это $O(n)$ операций (сортировка, пересчёт массива), даже мемоизация может не помочь. Иногда выручает change-tracking (хранить только изменения) или итеративный DP с rolling array.
• Задача про оптимум в непрерывном пространстве. Бинарный поиск, тернарный поиск, выпуклые оболочки — для них рекурсия не нужна. Перебор имеет смысл только в дискретных пространствах решений.

---

Связанные техники

• DP с явной таблицей. Естественный следующий шаг после мемоизации. Когда формула состоянного перехода устоялась, переписываем рекурсию в итеративный массив — это быстрее, меньше памяти, и проще профилировать.
• Bitmask DP. Когда состояние — подмножество, маска как индекс даёт компактный массив dp[mask] вместо cache[set]. Применимо при $n \le 22$.
• Meet-in-the-middle. Расширение перебора подмножеств на $n \le 40$: делим на две половины, перебираем каждую за $2^{n/2}$, соединяем через сортировку или хешмап.
• Branch and bound. Развитие отсечений: помимо отсечения по оценке, удерживаем приоритетную очередь поддеревьев и выбираем самое «перспективное». Используется в задачах оптимизации, где гарантия корректности отсечений тонкая.
• DFS на графе с состояниями. Когда «дерево решений» становится графом (некоторые состояния достижимы разными путями) — это DP/мемоизация на DAG. Принципиально тот же шаблон, что и в задаче 2, но интерпретация другая.

---

Итого

• Техника: рекурсия по дереву решений + откат + (опционально) отсечения и мемоизация.
• Сложность шаблона: $O(\text{число листьев дерева})$ для чистой рекурсии; $O(\text{состояний} \cdot \text{переход})$ с мемоизацией.
• Сигналы в условии: «перечислить все / сколько способов», маленькое $n$ ($\le 20$–$40$), маленькая ось «суммы / комбинации» ($\le 10^4$), древовидная структура выбора.
• Типичные ловушки: забытый откат, мемоизация с побочными эффектами, неполное состояние, ошибочные отсечения по эвристике.