Sumes iguals (3) P11655

Statement

Feu un programa que, donat un natural $s$ i $n$ naturals $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 natural $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

En aquest exercici, un algorisme molt simple pot ser massa lent.

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