Разделите веса
Дано n весов . Требуется распределить эти веса в две группы таким образом, чтобы разница между суммами этих групп была минимальной.
Входные данные
Первая строка содержит одно целое число n (1 ≤ n ≤ 20).
Во второй строке расположены n целых чисел, разделённых пробелами: (1 ≤ ≤ ).
Выходные данные
Программа должна вывести минимально возможную разницу между суммами двух групп.
Примеры
Входные данные | Выходные данные |
|---|---|
3 | 0 |
5 | 1 |
Пояснение
Первая группа → 3, вторая группа → 1 + 2 = 3
Первая группа → 1 + 7 = 8, вторая группа → 2 + 3 + 4 = 9
Подсказка
Вы можете перебрать все возможные варианты разбиения (их всего ) и вычислить минимальную разницу.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB