Somando moedas
Dadas
n moedas de determinado valor, pretende-se descobrir todos os somatórios possíveis que se podem obter com essas moedas.Entrada
A primeira linha da entrada contém um único inteiro
n (1 ≤ n ≤ 100).A linha seguinte contém
n inteiros separados por espaços (1 ≤ ≤ 1000), que representam os valores das moedas.Saída
O programa deve imprimir, na primeira linha, a quantidade de possíveis somas que podem ser obtidas. Já na segunda linha da saída, devem ser listadas todas as somas em ordem crescente, separadas por um espaço.
Exemplos
Entrada | Saída |
4
2 5 4 2 | 9
2 4 5 6 7 8 9 11 13 |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB