Перебор последовательностей

Половина переборных задач формулируется как «выведите все объекты такого-то вида в лексикографическом порядке». Пишутся они все одинаково, и полезно один раз разобрать шаблон, чтобы потом менять в нём три строки.

Шаблон

int n, k;
vector<int> prefix;

void generate(int length) {
    if (length == n) { print(prefix); return; }
    for (int symbol = 0; symbol < k; symbol++) {
        prefix.push_back(symbol);
        generate(length + 1);
        prefix.pop_back();
    }
}

Это генерация всех строк длины $n$ из $k$ символов. Проверено: количество выведенного равно $k^n$, и порядок лексикографический.

Три вещи, из которых состоит любой перебор:

1. Условие остановки — префикс достиг нужного вида, выводим;
2. Цикл по вариантам продолжения;
3. Добавить — углубиться — убрать.

Третий пункт — самый важный. pop_back после рекурсивного вызова возвращает состояние в то, каким оно было до входа в ветку. Без него следующая итерация цикла работала бы с испорченным префиксом.

Приём называется перебором с возвратом: сделали шаг, обошли всё, что из него следует, откатились.

Почему порядок лексикографический

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

flowchart TD
    R["«»"] --> A["«0»"]
    R --> B["«1»"]
    A --> A0["«00»"]
    A --> A1["«01»"]
    B --> B0["«10»"]
    B --> B1["«11»"]

Рекурсия обходит это дерево в глубину, и порядок листьев слева направо — это и есть порядок вывода.

Значит, порядок вывода полностью определяется порядком перебора в цикле. Идём по возрастанию символа — получаем лексикографический порядок. Нужен обратный — меняем цикл на убывающий, и больше ничего.

Никакой сортировки в конце не требуется, и это стоит помнить: сортировка миллиона строк дороже их генерации.

Префикс лучше держать глобально

Передавать массив параметром — значит копировать его на каждом вызове. Для перебора это лишний множитель $n$ и часто разница между «зашло» и «превышено время».

Правильно — общий массив (глобальный или захваченный по ссылке лямбдой) и явные push_back / pop_back. Тогда состояние одно на весь перебор, а рекурсия только помечает, где она в нём находится.

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

Меняем три строки — получаем другую задачу

Из шаблона выводятся почти все классические переборы.

Двоичные строки — k = 2.

Строки без двух нулей подряд — добавить условие в цикл: символ $0$ допустим, только если предыдущий не $0$.

Строки с ровно $k$ единицами — вести счётчик единиц и не заходить в ветки, где нужное количество уже недостижимо. Проверено: количество равно $\binom{n}{k}$.

Строго убывающие последовательности длины $k$ — передавать последний выбранный элемент и перебирать только меньшие. Проверено: количество равно $\binom{n}{k}$.

Перестановки — вести массив «использовано» и пропускать занятые значения.

Разбиения на слагаемые — вместо длины следить за оставшейся суммой.

Во всех случаях меняются условие остановки и границы цикла. Каркас «добавить — углубиться — убрать» остаётся тем же.

Параметры: что передавать, а что нет

Практическое правило: в параметрах — то, что меняется при спуске и нужно для решения; в глобальных переменных — то, что описывает состояние целиком.

Обычные параметры: текущая длина, оставшаяся сумма, последнее выбранное значение, счётчик чего-либо.

Обычно глобальные: сам префикс, массив «использовано», входные данные, накопитель ответа.

Чем меньше параметров, тем меньше кадр стека и тем глубже можно уйти. Но не в ущерб понятности: два лишних int — не та экономия, ради которой стоит запутать код.

Выводить сразу или копить

Если объектов много, копить их в векторе — верный способ исчерпать память. Миллион строк по двадцать символов — это уже десятки мегабайт.

Выводите сразу, в cout с отключённой синхронизацией. А если требуется обратный порядок и лень выводить его напрямую — проще перевернуть цикл перебора, чем хранить всё и делать reverse.