Considerăm un număr întreg N şi un şir de M cifre zecimale nenule. Să se determine dacă numărul N poate fi rezultatul unei expresii aritmetice simple (fără paranteze), formată exclusiv din cifrele şirului citit şi din operatorii aritmetici desemnaţi pentru operaţiile de adunare şi scădere (+, -).

Cerinţă

Scrieţi un program care citeşte numerele N şi M de pe prima linie a fişierului de intrare şi şirul de M cifre de pe linia următoare şi determină şi afişează expresia găsită sau valoarea 0 în cazul în care nu există soluţie.

Date de intrare

Fișierul de intrare adunscad.in conține pe prima linie numerele întregi N M, separate printr-un spaţiu, reprezentând valoarea ce trebuie obţinută la evaluarea expresiei şi numărul de cifre din şir. Linia a doua a fişierului de intrare conţine şirul celor M cifre nenule, separate prin câte un spaţiu.

Date de ieșire

Fișierul de ieșire adunscad.out va conține pe prima linie expresia determinată, în cazul în care există soluţie, sau valoarea 0 în cazul în care nu există soluţie.

Restricții și precizări

• -180 ≤ N ≤ 180
• 2 ≤ M ≤ 20
• în şirul citit cifrele se pot repeta
• toate cifrele din şir trebuie să apară şi în expresia aritmetică, în aceeaşi ordine în care au fost citite
• în expresia aritmetică, orice cifră trebuie să fie precedată de un operator; în cazul în care prima cifră este precedată de operatorul '+' acesta nu se pune în expresie
• în expresia aritmetică nu există spaţii
• expresia aritmetică se termină cu caracterul sfârşit de linie
• în cazul în care soluţia nu este unică se va afişa o soluţie corectă

Exemplu 1

adunscad.in

21 43 9 1 8

adunscad.out

3+9+1+8

Exemplu 2

adunscad.in

-1 41 2 3 5

adunscad.out

-1+2+3-5

Exemplu 3

adunscad.in

-7 71 1 1 1 1 1 1

adunscad.out

-1-1-1-1-1-1-1

Exemplu 4

adunscad.in

12 31 2 3

adunscad.out

0

#include <bits/stdc++.h>
using namespace std;

ifstream cin("adunscad.in");
ofstream cout("adunscad.out");

int n , x[25] , a[20] , nr , ok;

void afisare()
{
    if(ok == 0)
    {
        for(int i = 1 ; i <= n ; i++)
        {
            if(i == 1 && x[i] == 1) cout << a[i];
            else if(x[i] == -1) cout << "-" << a[i];
            else cout << "+" << a[i];
        }
        cout << '\n';
        ok++;
    }
}

void back(int k , int sp)
{
    for(int i = -1; i <= 1; i += 2)
    {
        x[k] = i;
        sp = sp + i * a[k];
        if(k == n)
        {
            if(sp == nr) afisare();
        }
        else back(k + 1 , sp);
        sp = sp - i * a[k];
    }
}

int main()
{
    cin >> nr >> n;
    for(int i = 1 ; i <= n ; i++)
        cin >> a[i];
    back(1 , 0);
    if(ok == 0) cout << 0;
}