Полный перебор и его границы

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

Полный перебор (brute force) — стратегия, при которой мы явно проверяем все возможные варианты ответа и выбираем подходящий.

Зачем это нужно

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

Перебор подмножеств: 2^n вариантов

У множества из n элементов ровно 2^n подмножеств: каждый элемент либо взят, либо нет. Классический приём — сопоставить подмножеству число от 0 до 2^n − 1 и читать его биты: бит i равен 1 ⇔ элемент i входит в подмножество. Но в Python удобнее и нагляднее воспользоваться itertools.combinations. Решим задачу: есть ли подмножество с заданной суммой.

from itertools import combinations

a = [3, 34, 4, 12, 5, 2]
target = 9
found = None
for r in range(len(a) + 1):              # размер подмножества: 0..n
    for combo in combinations(a, r):     # все сочетания этого размера
        if sum(combo) == target:
            found = combo
            break
    if found:
        break
print("Подмножество с суммой", target, ":", found)

Внешний цикл перебирает размер подмножества, внутренний — все сочетания этого размера. Суммарно мы проходим все 2^n подмножеств. Для n=6 это 64 варианта — мгновенно; для n=40 это уже 10^12 — безнадёжно.

Вывод:

Подмножество с суммой 9 : (4, 5)

Битовый способ перебора подмножеств

На олимпиадах чаще пишут перебор через биты — он быстрее и не требует библиотек. Идея: число mask от 0 до 2^n−1 кодирует подмножество.

a = [3, 34, 4, 12, 5, 2]
target = 9
n = len(a)
answer = None
for mask in range(1 << n):              # 1<<n == 2**n
    s = 0
    for i in range(n):
        if mask & (1 << i):             # i-й бит установлен?
            s += a[i]
    if s == target:
        answer = [a[i] for i in range(n) if mask & (1 << i)]
        break
print("Найдено подмножество:", answer)

Здесь mask & (1 << i) проверяет, включён ли i-й элемент. Такой шаблон встречается постоянно — например, в ДП по подмножествам (битовая динамика). Запомни: 1 << n — это 2^n, а mask & (1 << i) — проверка бита.

Вывод:

Найдено подмножество: [4, 5]

Перебор перестановок: n! вариантов

Когда важен порядок (например, задача коммивояжёра на малом числе городов), перебирают перестановки. Их n!, что растёт ещё быстрее: 10! ≈ 3.6·10^6 (ок), 13! ≈ 6·10^9 (уже нет). В Python — itertools.permutations.

from itertools import permutations

# кратчайший маршрут, который посещает все точки (мини-коммивояжёр)
dist = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0],
]
n = len(dist)
best = float("inf")
for perm in permutations(range(1, n)):   # 0 фиксируем как старт
    route = [0] + list(perm)
    cost = sum(dist[route[i]][route[i + 1]] for i in range(n - 1))
    best = min(best, cost)
print("Минимальная стоимость маршрута:", best)

Мы фиксируем стартовый город 0 (иначе считали бы один и тот же цикл n раз) и перебираем порядок остальных. Для n=4 это 3! = 6 маршрутов.

Вывод:

Минимальная стоимость маршрута: 65

Где проходит граница

Тип перебора	Сложность	Предел n
Все пары	`O(n^2)`	~5000
Подмножества	`O(2^n · n)`	~20–22
Перестановки	`O(n!)`	~10–11

Если n чуть больше границы, есть приёмы: meet-in-the-middle делит множество пополам и сводит 2^n к 2^(n/2) (поднимает предел подмножеств до ~40), а отсечения (branch and bound) обрезают заведомо плохие ветки. Но сначала всегда оценивай: а пройдёт ли честный перебор?

Подводные камни

Не путай 2^n (подмножества) и n^2 (пары) — это совершенно разные масштабы.
Перебор перестановок легко сделать вдвое-вшестеро быстрее, зафиксировав часть порядка (как старт 0 выше).
Перебор — лучший друг при отладке: им проверяют хитрые решения на случайных тестах (стресс-тест, см. раздел 7).

Итог

Полный перебор проверяет все варианты — он прост, надёжен и хорош как эталон.
Подмножества: 2^n, предел n ≈ 20; перестановки: n!, предел n ≈ 10.
Битовая маска mask элегантно кодирует подмножество; mask & (1 << i) — проверка бита.
Если перебор не проходит — думай про meet-in-the-middle, отсечения или другой класс алгоритма.