Сколько стоит перебор

Перед тем как писать перебор, полезно знать, влезет ли он. Ответ определяется одним числом — количеством объектов, — и таблицей ниже.

Замеры

На одной машине, GCC с -O2, пустое тело цикла:

перебор	количество	время
$2^{20}$ масок	$10^6$	3 мс
$2^{24}$ масок	$1.7 \cdot 10^7$	31 мс
$2^{26}$ масок	$6.7 \cdot 10^7$	98 мс
$10!$ перестановок	$3.6 \cdot 10^6$	9 мс
$11!$ перестановок	$4 \cdot 10^7$	95 мс
$12!$ перестановок	$4.8 \cdot 10^8$	1120 мс

С содержательной обработкой каждого варианта время растёт в несколько раз, поэтому запас нужен минимум десятикратный.

Рабочие границы

объект	сколько их	предел
подмножества $2^n$	—	$n \le 25$
перестановки $n!$	—	$n \le 11$
сочетания $\binom{n}{k}$	зависит от $k$	считать явно
разбиения $p(n)$	$p(60) \approx 10^6$	$n \le 70$
скобочные, число Каталана	$C_{20} \approx 6.6 \cdot 10^9$	$n \le 15$
строки длины $n$ из $k$ букв	$k^n$	$k^n \le 10^7$

Обратите внимание на сочетания: $\binom{30}{2} = 435$, а $\binom{30}{15} = 155\,117\,520$. Одна и та же формулировка «выберите $k$ из $n$» может быть и мгновенной, и безнадёжной — надо считать.

Ограничения подсказывают метод

Обратная задача — по ограничениям угадать ожидаемое решение. Обычно это работает:

$n$ в условии	что от вас ждут
$\le 10$	перестановки, полный перебор
$\le 20$	подмножества, динамика по маскам $2^n \cdot n$
$\le 40$	встреча посередине
$\le 100$	кубическая динамика или перебор с сильными отсечениями
$\le 5000$	квадрат
$\le 10^5$	$n \log n$
$\le 10^7$	линия

Строка «$\le 40$» самая характерная: такое ограничение почти никогда не случайно.

Встреча посередине

Приём для $n$ около 40, когда $2^n$ недостижимо, а $2^{n/2}$ — вполне.

Идея: разбить объекты на две половины по $n/2$, перебрать все подмножества каждой отдельно ($2^{20} \approx 10^6$ штук), а затем склеить половины бинарным поиском или двумя указателями.

// суммы всех подмножеств первой половины
vector<long long> first;
for (int mask = 0; mask < (1 << half); mask++) {
    long long sum = 0;
    for (int i = 0; i < half; i++) if (mask >> i & 1) sum += a[i];
    first.push_back(sum);
}
sort(first.begin(), first.end());

// для каждой суммы второй половины ищем дополнение
for (int mask = 0; mask < (1 << (n - half)); mask++) {
    long long sum = 0;
    for (int i = 0; i < n - half; i++) if (mask >> i & 1) sum += a[half + i];
    answer += upper_bound(first.begin(), first.end(), target - sum)
            - lower_bound(first.begin(), first.end(), target - sum);
}

Итог — $O(2^{n/2} \cdot n)$ вместо $O(2^n)$. Для $n = 40$ это разница между секундой и тысячей лет.

Ограничение метода: половины должны быть независимы, а способ склейки — быстрым. Для сумм это работает; для задач, где элементы взаимодействуют произвольно, — нет.

Что делать, когда не влезает

По убыванию предпочтительности:

1. Отсечения. Дёшево, иногда достаточно.
2. Мемоизация. Если разные ветки приходят в одно состояние — перебор превращается в динамику.
3. Динамика по подмножествам. $2^n \cdot n$ вместо $n!$ — стандартный ход для задачи коммивояжёра и её родственников.
4. Встреча посередине. Когда $n$ около 40.
5. Полиномиальный алгоритм. Часто задача просто не про перебор, и стоит перечитать условие.

Пункт пятый не шутка: ограничение вида $n \le 10^5$ рядом со словом «переберите» означает, что перебирать надо не то, что кажется.

И про замеры

Приведённые числа — ориентир, а не закон. Реальная скорость зависит от машины, компилятора, обращений к памяти и того, что происходит внутри цикла.

Поэтому единственный надёжный способ узнать, влезет ли решение, — запустить его на максимальном тесте локально. Прикидка отвечает на вопрос «стоит ли вообще писать»; замер — на вопрос «пройдёт ли».