Equal sums (2) P82660
Write a program that, given an integer number s and n integer numbers x1, …, xn, prints the subset (maybe with repeated numbers, but using every xi at most once) lexicographically largest among those whose sum is s.
Input
Input consists of an integer number s, followed by a number n > 0, followed by x1, …, xn.
Output
Print, with the elements sorted non-increasingly, the subset that is greatest in lexicographical order among those that can be made up with x1, …, xn and whose sum is s. If there is none, print “no solution”.
Hint
Sort the given numbers.
Public test cases
Input
6 7 1 6 0 1 3 2 0
Output
{6,0,0}
Input
-5 3 6 -10 4
Output
no solution
Input
-5 9 3 1 -1 -1 0 -3 0 -2 2
Output
{2,0,0,-1,-1,-2,-3}
Input
-9 3 -5 6 -4
Output
{-4,-5}
Information
- Author
- Salvador Roura
- Language
- English
- Translator
- Carlos Molina
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++