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++
- User solutions
- C++