# include < iostream >
# include < cstring >
using namespace std ;
typedef int stiva[ 100 ];
int n; // numarul de cifre al numarului
int s; // suma cifrelor cautate
stiva st; // stiva de selectie
int viz [ 10 ]; // vector de vizitare a cifrelor
// initializare stiva
void init ( int k) {
st[k] = 0 ;
}
// functia de generare a succesorilor
int succesor ( int k) {
if (st[k] < 9 ) {
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 && ! viz [st[k]];
}
// functia de afisare a solutiei
void tipar () {
cout << "{" ;
for ( int i = 1 ; i <= n; i++) {
cout << st[i];
}
cout << "}" << endl ;
}
// functia de backtracking
void bt ( int k, int sum ) {
init (k);
while ( succesor (k)) {
if ( valid (k, sum + st[k])) {
viz [st[k]] = 1 ;
if ( solutie (k, sum + st[k])) {
tipar ();
} else {
bt (k+ 1 , sum + st[k]);
}
viz [st[k]] = 0 ;
}
}
}
int main () {
// citirea datelor de intrare
cout << " Introduceti numarul de cifre al numarului : " ;
cin >> n;
cout << " Introduceti suma cifrelor: " ;
cin >> s;
// apelul functiei de backtracking
bt ( 1 , 0 );
return 0 ;
}
Introduceti numarul de cifre al numarului : 3
Introduceti suma cifrelor: 11
{128}
{137}
……………………………………………………………………………….
{812}
{821}