# include < iostream >
# include < cstring >
using namespace std ;
typedef int stiva[ 100 ];
int n; // numarul de elemente ale multimi
int s; // suma elementelor cautate
int a[ 100 ]; // vectorul de elemente ale multimii
stiva st; // stiva de selectie
// initializare stiva
void init ( int k) {
st[k] = 0 ;
}
// 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, int sum ) {
return k == n && sum == s;
}
// functia de verificare a validitatii solutiei partiale
int valid ( int k, int sum ) {
return sum <= s;
}
// functia de afisare a solutiei
void tipar ( int sum ) {
cout << "{" ;
int x = 0 ;
for ( int i = 1 ; i <= n; i++) {
if (st[i] == 1 ) {
if (x > 0 ) {
cout << ", " ;
}
cout << a[i];
x++;
}
}
cout << "} (suma = " << sum << ")" << endl ;
}
// functia de backtracking
void bt ( int k, int sum ) {
init (k);
while ( succesor (k)) {
int newsum = sum + a[k] * st[k];
if ( valid (k, newsum )) {
if ( solutie (k, newsum )) {
tipar ( newsum );
} else {
bt (k+ 1 , newsum );
}
}
}
}
int main () {
// citirea datelor de intrare
cout << " Introduceti numarul de elemente ale multimii : " ;
cin >> n;
cout << " Introduceti elementele multimii : " ;
for ( int i = 1 ; i <= n; i++) {
cin >> a[i];
}
cout << " Introduceti valoarea pentru suma: " ;
cin >> s;
// apelul functiei de backtracking
bt ( 1 , 0 );
return 0 ;
}
Acest program citește numărul de elemente ale mulțimii, elementele mulțimii și valoarea pentru suma de la tastatură și apoi apelează funcția bt pentru a genera toate submulțimile cu suma elementelor egală cu s.
Pentru a rula programul, trebuie să introduceți datele de intrare la tastatură în formatul specificat în enunțul problemei.
E xemplu de date de intrare:
Introduceti numarul de elemente ale multimii : 5
Introduceti elementele multimii : 3 5 2 7 1
Introduceti valoarea pentru suma: 10
Acest exemplu va genera toate submulțimile mulțimii {3, 5, 2, 7, 1}