Write a program that, given a natural number s
and n natural numbers x_{1}, …, x_{n},
prints all the subsets
(maybe with repeated numbers, but using every x_{i} at most once)
whose sum is exactly s.

Input

Input consists of a natural number s,
followed by a number n > 0,
followed by x_{1}, …, x_{n}.

Output

Print all the subsets whose sum is s
that can be made up with x_{1}, …, x_{n}.

You can print in any order both the solutions and the elements inside each solution.

Hint

For this exercise, a very simple algorithm can be too slow.

Public test cases

**Input**

6 7 1 6 0 1 3 0 2

**Output**

{1,3,2} {1,3,0,2} {0,1,3,2} {0,1,3,0,2} {6} {6,0} {6,0} {6,0,0} {1,3,2} {1,3,0,2} {1,0,3,2} {1,0,3,0,2}

**Input**

10 10 1 1 1 1 1 1 1 1 1 1

**Output**

{1,1,1,1,1,1,1,1,1,1}

Information

- Author
- Salvador Roura
- Language
- English
- Translator
- Carlos Molina
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++ Python Python
- User solutions
- C++