BKT Hub — Cifre Distincte

🔢 Problema

Se citește un număr natural n (recomandat n < 15). Să se genereze toate numerele formate din cifre distincte a căror sumă a cifrelor este exact n.

Exemplu: n = 3 → 3, 12, 21, 30, 102, 120, 201, 210

Cifrele nu pot fi repetate în același număr. Prima cifră nu poate fi 0 (fără zerouri conducătoare).

🔁 Abordarea BKT

Construim numărul cifră cu cifră în vectorul x[1..k]. La fiecare poziție k încercăm cifrele de la 0 la 9.

Validitate: cifra curentă să nu mai apară anterior (x[k] ≠ x[i] pentru i < k) și suma parțială să nu depășească n.

Soluție: suma cifrelor x[1..k] este exact n. INIT(1)=0 previne zerouri conducătoare (prima cifră pornește de la 1).

💻 Cod C++ — Cifre Distincte BKT

💻 Cod C++

// se citeste un numar natural n (recomandat < 15). // sa se genereze toate numerele din cifre distincte, care au suma // cifrelor = cu n . ex n=3 => 102, 12, 120, 201, 21, 210, 3, 30 #include<iostream> using namespace std; int x[10],n,sol=0,s; void INIT(int k) { if (k==1) x[k]=0; else x[k]=-1; } int EXISTA(int k) { if(x[k]<9) return 1; else return 0; } int VALID(int k) { int i; s=0; for(i=1;i<k; i++) if(x[k]==x[i]) return 0; for(i=1;i<=k; i++) s=s+x[i]; if(s>n) return 0; return 1; } int SOLUTIE(int k) { if(s==n) return 1; else return 0; } void TIPAR(int k) { int i; sol++; for(i=1; i<=k; i++) cout<<x[i]; cout<<endl; } void BCK() { int k=1; INIT(k); while(k>0) if(EXISTA(k)) { x[k]++ ; if(VALID(k)) if(SOLUTIE(k)) { TIPAR(k); k++; INIT(k);} else { k++; INIT(k);} } else k--; } int main() { cout<<"n="; cin>>n; BCK(); cout<<"S-au generat "<<sol<<" solutii."; }

n =

Viteză: 5×

Configurează n și apasă ⚙ Generează

Numărul curent

—

Soluții găsite

numere cu suma = n

Adâncime curentă

cifre în construcție

Reveniri (BKT)

backtrack-uri totale

Configurează n și apasă ⚙ Generează

Pas: 0 / —