# include < iostream >
using namespace std ;
const int MAX_N = 100 ;
int n, x;
int cifre[MAX_N];
int st[MAX_N];
int m;
void init ( int k) {
st[k] = -1 ;
}
int succesor ( int k) {
if (st[k] < m -1 ) {
st[k]++;
return 1 ;
} else {
return 0 ;
}
}
int valid ( int k) {
int numar = 0 ;
for ( int i = 0 ; i <= k; i++) {
numar = numar * 10 + cifre[st[i]];
}
return cifre[st[ 0 ]] != 0 && numar < x;
}
int solutie ( int k) {
return k == m -1 ;
}
void tipar () {
int numar = 0 ;
for ( int i = 0 ; i < m; i++) {
numar = numar * 10 + cifre[st[i]];
}
cout << numar << " " ;
}
void bt ( int k) {
init (k);
while (succesor(k)) {
if (valid(k)) {
if ( solutie (k)) {
tipar();
} else {
bt (k+ 1 );
}
}
}
}
int main () {
cout << "n = " ; cin >> n;
cout << "Cifrele: " ;
for ( int i = 0 ; i < n; i++) {
cin >> cifre[i];
}
cout << "x = " ; cin >> x;
int temp = x;
m = 0 ;
while ( temp > 0 ) {
temp /= 10 ;
m++;
}
bt ( 0 );
return 0 ;
}
Această soluție folosește un tablou cifre pentru a stoca cifrele distincte introduse de la tastatură, un tablou st pentru a stoca soluția parțială curentă și variabilele m și x pentru a stoca numărul de cifre al lui x și numărul x introdus de la tastatură. Funcția init inițializează stiva cu valoarea -1 , succesor generează următorul element din stivă, valid verifică dacă soluția parțială curentă este validă, solutie verifică dacă soluția parțială curentă este o soluție completă, iar tipar afișează soluția curentă.
Funcția bt implementează algoritmul de backtracking . De asemenea, în funcția main se calculează numărul de cifre m ale lui x și se apelează funcția bt cu indicele inițial 0 .
Un exemplu de date de intrare ar putea fi:
n = 4 (numărul de cifre) cifre = {1, 3, 5, 7}