# include < iostream >
# include < cstring >
using namespace std ;
typedef int stiva[ 100 ];
int n; // numarul de elemente
int a[ 100 ]; // vectorul de elemente
char b[ 200 ]; // secvența de operatori (+ sau -)
int s; // suma curentă
stiva st; // stiva de selectie
// initializare stiva
void init ( int k) {
st[k] = -1 ;
}
// functia de generare a succesorilor
int succesor ( int k) {
if (st[k] < 1 ) {
st[k]++;
return 1 ;
} else {
return 0 ;
}
}
// functia de verificare a solutiei
int solutie ( int k) {
return k == n -1 && s > 0 ;
}
// functia de verificare a validitatii solutiei partiale
int valid ( int k) {
return 1 ;
}
// functia de afisare a solutiei
void tipar () {
cout << a[ 0 ];
for ( int i = 0 ; i < n -1 ; i++) {
cout << " " << b[i] << " " << a[i+ 1 ];
}
cout << " = " << s << endl ;
}
// functia de backtracking
void bt ( int k) {
init (k);
while ( succesor (k)) {
if (st[k] == 0 ) {
b[k] = '+' ;
s += a[k+ 1 ];
} else {
b[k] = '-' ;
s -= a[k+ 1 ];
}
if ( valid (k)) {
if ( solutie (k)) {
tipar ();
} else {
bt (k+ 1 );
}
}
if (st[k] == 0 ) {
s -= a[k+ 1 ];
} else {
s += a[k+ 1 ];
}
}
}
int main () {
// citirea datelor de intrare
cout << " Introduceti numarul de elemente: " ;
cin >> n;
cout << " Introduceti elementele: " ;
for ( int i = 0 ; i < n; i++) {
cin >> a[i];
}
// inițializați suma 's' cu primul element al vectorului 'a'
s = a[ 0 ];
// apelul functiei de backtracking
bt ( 0 );
return 0 ;
}