Equal sums (3) P11655


Statement
 

pdf   zip

thehtml

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

Input

Input consists of a natural number s, followed by a number n > 0, followed by x1, …, xn.

Output

Print all the subsets whose sum is s that can be made up with x1, …, xn.

Information about the checker

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++ Python