Divida os pesos
Dado n pesos , é solicitado que sejam divididos em 2 grupos de forma que a diferença entre as somas desses grupos seja a menor possível.
Entrada
A primeira linha da entrada contém um único inteiro n (1 ≤ n ≤ 20).
A linha seguinte contém n inteiros separados por espaços (1 ≤ ≤ ).
Saída
O programa deve imprimir a menor diferença possível entre os dois grupos.
Exemplos
Entrada | Saída |
|---|---|
3 | 0 |
5 | 1 |
Explicação
Primeiro grupo → 3, segundo grupo → 1 + 2 = 3
Primeiro grupo → 1 + 7 = 8, segundo grupo → 2 + 3 + 4 = 9
Dica
Pode tentar dividir os pesos em todas as possíveis combinações para calcular a menor diferença possível.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB