Partițiile unui număr prin backtracking în C++

O partiție a lui n este o scriere a lui ca sumă de numere întregi pozitive, în care ordinea termenilor nu contează. Pentru 4, partițiile sunt 1+1+1+1, 1+1+2, 1+3, 2+2 și 4. Scrierile 1+3 și 3+1 reprezintă aceeași partiție.

O ordine canonică elimină duplicatele

Generăm termenii în ordine nedescrescătoare. După ce am ales un termen x, următorul trebuie să fie cel puțin x. Astfel fiecare partiție are o singură reprezentare generată, cea cu termenii ordonați.

Citim 1≤n≤20 și afișăm toate partițiile, câte una pe linie, cu termenii separați prin spații. Ordinea afișării este cea dată de încercarea termenilor crescător. Tabloul clasic are capacitatea 20, deoarece o sumă n are cel mult n termeni pozitivi.

Ce păstrează apelul recursiv

Backtracking înseamnă construirea treptată a soluției prin încercări, urmate de revenirea la alegeri anterioare. Funcția primește restul încă neacoperit, valoarea minimă permisă pentru următorul termen și numărul k de termeni deja aleși.

Dacă restul este zero, termenii din a[0..k-1] formează o soluție completă. Altfel încercăm x de la minim la rest, îl scriem în a[k] și continuăm cu rest-x. După întoarcere, aceeași poziție poate fi suprascrisă de următoarea alegere.

Partițiile lui 4 sunt 1+1+1+1, 1+1+2, 1+3, 2+2 și 4. Ordinea nedescrescătoare exclude duplicatul 3+1.Mărește schema ↗

Varianta cu tablou clasic

#include <iostream>
using namespace std;
int a[20];
void genereaza(int rest,int minim,int k) {
    if(rest==0) {
        for(int i=0;i<k;++i) cout << (i?" ":"") << a[i];
        cout << '\n'; return;
    }
    for(int x=minim;x<=rest;++x) { a[k]=x; genereaza(rest-x,x,k+1); }
}
int main() {
    int n; cin >> n;
    genereaza(n,1,0);
}

Varianta echivalentă cu std::vector

Păstrăm limitele intrării și aceleași rezultate. Tabloul clasic rezervă capacitatea maximă; vectorul construiește numărul de elemente necesare. Indicii folosiți de algoritm rămân aceiași.

#include <vector>

#include <iostream>
using namespace std;
vector<int> a;
void genereaza(int rest,int minim,int k) {
    if(rest==0) {
        for(int i=0;i<k;++i) cout << (i?" ":"") << a[i];
        cout << '\n'; return;
    }
    for(int x=minim;x<=rest;++x) { a[k]=x; genereaza(rest-x,x,k+1); }
}
int main() {
    int n; cin >> n; a.resize(n);
    genereaza(n,1,0);
}

De ce nu afișăm și 3+1

La n=4, ramura care începe cu 1 poate continua cu 3 și produce 1+3. Ramura care începe cu 3 are restul 1, dar următorul termen trebuie să fie cel puțin 3. Bucla nu are nicio alegere și ramura se încheie. Nu mai trebuie o listă de soluții anterioare pentru eliminarea duplicatelor.

Fiecare apel micșorează restul cu cel puțin unu, deci recursia se termină. Orice partiție poate fi ordonată nedescrescător și apare pe ramura care alege exact termenii ei. Restricția de ordine nu elimină o soluție distinctă.

Memoria pentru soluție și apeluri este O(n). Timpul depinde de numărul partițiilor afișate; dacă îl notăm p(n), o limită superioară este O(n·p(n)), incluzând scrierea termenilor. Nu este o simplă parcurgere liniară a lui n.

Exersează

Pentru 1 se afișează doar 1. Pentru 3 se afișează 1 1 1, 1 2, 3. Verifică faptul că fiecare linie are suma cerută și termeni nedescrescători. Ca extensie, cere termeni strict crescători și schimbă limita minimă transmisă apelului următor.

Revezi backtracking pentru permutări, combinările și recursivitatea.

Întrebări frecvente

Ce este o partiție a unui număr natural?

O scriere a numărului ca sumă de întregi pozitivi în care ordinea termenilor nu contează. Pentru 4, scrierile 1+3 și 3+1 reprezintă aceeași partiție.

Cum evit generarea aceleiași partiții în mai multe ordini?

Construiește termenii în ordine nedescrescătoare. După alegerea lui x, impune ca următorul termen să fie cel puțin x. Fiecare partiție rămâne reprezentată o singură dată.

Când am găsit o partiție completă în backtracking?

Când suma rămasă de completat este zero. Atunci termenii aleși alcătuiesc o soluție. Dacă mai există rest, continuă numai cu termeni pozitivi care nu îl depășesc.