Write a program that, given an integer number *s*
and *n* integer 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 an integer 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, simple backtracking solutions are accepted. No optimizations are required.

Public test cases

**Input**

6 7 1 -2 0 3 -4 5 1

**Output**

{5,1} {0,5,1} {-2,3,5} {-2,0,3,5} {1,5} {1,3,-4,5,1} {1,0,5} {1,0,3,-4,5,1}

**Input**

0 2 -5 5

**Output**

{} {-5,5}

Information

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