Две команды для школьного матча

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

Нужно найти минимально возможную разницу между суммами сил двух команд.

Формат ввода

В первой строке дано целое число n — число учеников. Во второй строке дано n целых чисел a1, a2, ..., an — силы учеников.

Формат вывода

Выведите одно целое число — минимально возможное значение |S1 - S2|, где S1 и S2 — суммы сил в двух командах.

Ограничения

• 2 ≤ n ≤ 20
• 1 ≤ ai ≤ 100000

Пример

Ввод:

4
10 20 15 5

Вывод:

0

Пояснение: можно разделить как (10+15) и (20+5), суммы равны 25 и 25.

Ключевое наблюдение: если выбрать первую команду как подмножество с суммой S, то сумма второй — total - S. Разница тогда равна |(total - S) - S| = |total - 2*S|. Значит, задача — найти такое S (сумму какого-то подмножества), чтобы |total - 2*S| было минимальным.

Почему работает перебор: n ≤ 20, значит подмножеств всего 2^n (максимум 1 048 576) — это реально перебрать за секунды.

План решения:

• Считай n и массив сил a.
• Посчитай total = sum(a) и заведи ответ best = total.
• Для каждой маски mask от 0 до (1<<n)-1:
• Посчитай сумму S элементов, где i-й бит маски равен 1.
• Вычисли текущую разницу diff = abs(total - 2*S) и обнови best.
• Если best == 0, можно сразу остановиться (лучше уже не будет).

Мини-сниппет формулы: diff = abs(total - 2*S)

Сложность: по времени O(n * 2^n) в лоб (для каждой маски смотрим биты), по памяти O(1).

Частая ошибка: пытаться перебрать разбиения «две команды» напрямую и считать обе суммы каждый раз. Достаточно хранить сумму только одной команды (подмножества), вторая получается как total - S, иначе легко получить лишний множитель 2 и запутаться с формулой разницы.