Sumes iguals (1) P40685

Statement

Feu un programa que, donat un enter $s$ i $n$ enters $x_1, \dots, x_n$ , escrigui tots els subconjunts (amb repetits o no, però usant cada $x_i$ com a molt un cop) que tinguin suma $s$ .

Entrada

L’entrada consisteix en un enter $s$ , seguit d’un nombre $n > 0$ , seguit de $x_1, \dots, x_n$ .

Sortida

Escriviu tots els subconjunts de suma $s$ que es poden formar amb $x_1, \dots, x_n$ .

Informació sobre el corrector

Podeu escriure en qualsevol ordre tant les solucions com els elements dins de cada solució.

Pista

Per a aquest exercici, el Jutge accepta solucions senzilles de tornada enrera. No cal fer cap optimització especial.

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: Catalan
Other languages: English
Official solutions: C++ Python Python
User solutions: C++ Python