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