ЕГЭОГЭЕНТ
РУҚА
Задания № 24, 27 · ЕГЭ

Перебор комбинаций

Как перечислять варианты и отбирать подходящие комбинации
3 мин чтенияСложность: Обновлено 29 сентября 2026

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

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

Сначала определяют, что именно выбирается, сколько позиций имеет вариант и какие значения разрешены на каждой позиции. Затем варианты строятся один за другим. После завершения построения проверяется ограничение: например, сумма чисел, отсутствие повторений, порядок элементов или соответствие маске слова.

Связь с полным перебором

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

\[N = \prod_{i=1}^{k} m_i\]

Здесь \(k\) — число позиций, а \(m_i\) — количество допустимых значений для \(i\)-й позиции. Если для всех позиций доступно по \(m\) значений, то \(N=m^k\). При запрете повторений число вариантов меняется: для \(k\) позиций из \(n\) различных элементов оно равно \(n\cdot(n-1)\cdot\ldots\cdot(n-k+1)\).

№
Пример

Нужно составить трёхзначные коды из цифр 1, 2, 3, 4 без повторений и посчитать коды, в которых сумма цифр больше 8. Перебираются \(4\cdot3\cdot2=24\) упорядоченных кода. Затем для каждого проверяется сумма; подходят только варианты с суммой 9.

!
Не путайте

Комбинация и перестановка — не одно и то же. При комбинации порядок обычно не важен, а в задачах на коды или последовательности порядок важен: 123 и 321 считаются разными вариантами. Для систематического построения таких последовательностей используют построение перестановок.

Проверьте себя

Сколько упорядоченных двухзначных кодов можно составить из цифр 1, 2, 3, 4 без повторений?

Главное за минуту

Главное

  • Перебор комбинаций строит и проверяет все варианты, удовлетворяющие правилам построения.
  • Число вариантов находят умножением количества выборов для каждой позиции; при запрете повторений число выборов уменьшается.
  • Если ветвь уже нарушает условие, бэктрекинг позволяет не достраивать её до конца.