Backtracking

1. Având rădăcina unui arbore binar, returnează toate căile de la rădăcină la frunză în orice ordine.
O frunză este un nod fără copii.

Reprezentarea unei soluții

O soluție completă S este un șir ordonat de noduri: S=(n1,n2,…,nk)
unde:
• n1=r (rădăcina)
• nk=f (o frunză)
• Pentru orice i, ni+1 este un copil al lui ni.
Astfel, S reprezintă o cale de la rădăcină la frunză.

Soluții parțiale
O soluție parțială P este un prefix al unei soluții complete: P=(n1,n2,…,nm) unde m≤k, iar
pentru orice i, ni+1 este copilul lui ni. Soluția parțială reprezintă o cale de la rădăcină către un
nod intermediar din arbore.

Succesori direcți ai unei soluții parțiale

Date fiind nodurile din P, nm este ultimul nod din soluția parțială. Sucesorii direcți ai lui P
sunt toate soluțiile parțiale obținute prin adăugarea unui copil al nodului nm: P′=(n1,n2,…,nm,c)
unde c∈{copiii lui nm}.
Dacă nm este frunză (nu are copii), atunci P este o soluție completă și nu are succesori.

Condiția de viabilitate pentru o soluție parțială

O soluție parțială este viabilă dacă:
• Există o cale validă în arbore, respectând legătura părinte-copil, de la rădăcină către nodul
final vm.
• Cu alte cuvinte, soluția parțială este un drum corect de la rădăcină către nodul curent.
• Nu trebuie să mai verificăm altceva, pentru că orice prefix de drum este viabil (deoarece
arborele este aciclic).

2. Un ceas binar are 4 LED-uri în partea de sus pentru a reprezenta orele (0-11) și 6 LED-uri în
partea de jos pentru a reprezenta minutele (0-59). Fiecare LED reprezintă un zero sau un unu, cu cel
mai puțin semnificativ bit în dreapta. Având un număr întreg turnedOn care reprezintă numărul de
LED-uri aprinse în prezent (ignorând PM), returnați toate orele posibile pe care ceasul le-ar putea
reprezenta. Puteți returna răspunsul în orice ordine. Ora nu trebuie să conțină un zero în față. De
exemplu, „01:00” nu este valid. Ar trebui să fie „1:00”. Minutul trebuie să conțină două cifre și
poate conține un zero în față. De exemplu, „10:2” nu este valid. Ar trebui să fie „10:02”.

Reprezentarea unei soluții

Matematic, o soluție completă este un șir binar de 10 cifre (LED-uri), cu:
• primii 4 biți pentru oră, H=(h3h2h1h0)
• următorii 6 biți pentru minute, M=(m5m4m3m2m1m0)
unde hi,mj∈{0,1}.
 Soluția completă S este un vector binar: S=(b1,b2,…,b10),bi∈{0,1}
cu condiția că:
• numărul de biți aprinși (1) în S este exact turnedOn,
• ora H este un număr valid 0≤H≤11,
• minutul M este un număr valid 0≤M≤59,
• ora nu începe cu zero în reprezentarea decimală (ex: ora 01 nu este permisă, trebuie 1).

Soluții parțiale
O soluție parțială P este o secvență parțială de biți: P=(b1,b2,…,bk),k≤10 care reprezintă
primii k LED-uri ale ceasului. Aceasta poate fi interpretată ca:
• dacă k≤4, avem doar biții pentru oră parțială,
• dacă k>4, primii 4 sunt pentru oră, restul pentru minute.

Succesorii direcți ai unei soluții parțiale

Dintr-o soluție parțială P=(b1,…,bk), succesorii direcți sunt două soluții parțiale noi: P
′=(b1,…,bk,0) sau P′′=(b1,…,bk,1). Adică următorul bit poate fi 0 sau 1.

Condiția de viabilitate
O soluție parțială P=(b1,…,bk) este viabilă dacă:
• Numărul de biți aprinși c=∑i=1kbi nu depășește turnedOn.
• Dacă k=4 (s-a completat ora), valoarea ora reprezentată H este validă 0≤H≤11.
• Dacă k=10, minutul M este valid 0≤M≤59.
• Dacă k=4, ora nu are zero în față în forma zecimală (ex: dacă bitul cel mai semnificativ b1
=0, iar ora nu este zero, este invalid; dar dacă ora = 0, este permis). Practic ora trebuie
interpretată corect când construim formatul final.

3. Suma XOR a unui tablou este definită ca XOR bit cu bit al tuturor elementelor sale, sau 0 dacă
tablou este gol. De exemplu, suma XOR a tabloului [2,5,6] este 2 XOR 5 XOR 6 = 1. Dat fiind un
tablou nums, returnează suma tuturor sumelor XOR pentru fiecare subset al nums. Notă: Subseturile
cu aceleași elemente trebuie numărate de mai multe ori. Un array a este un subset al unui array b
dacă a poate fi obținut din b prin ștergerea unor elemente (posibil zero) din b.

Reprezentarea unei soluții

O soluție completă este un subset S al vectorului nums, adică o secvență de alegeri care
includ sau exclud fiecare element ni. Matematic, putem reprezenta fiecare subset S printr-un vector
binar de lungime m: S=(s1,s2,…,sm),si∈{0,1} unde:
• si=1 înseamnă că ni este inclus în subset,
• si=0 înseamnă că ni este exclus.
Astfel, soluția completă este o alegere a valorilor si pentru toți i∈{1,…,m}.

Soluții parțiale
O soluție parțială este o alegere pentru primii k≤m indici: P0=(s1,…,sk,0) si P1=(s1,…,sk,1)
adică alegem să excludem sau să includem elementul nk+1.

Condiția de viabilitate a unei soluții parțiale

Orice soluție parțială este viabilă în această problemă, deoarece nu există constrângeri
suplimentare în alegerea subsetului.
4. Având un șir care conține cifre de la 2 la 9 inclusiv, returnează toate combinațiile posibile de
litere pe care le-ar putea reprezenta numărul. Returnează răspunsul în orice ordine.

Reprezentarea unei soluții

O soluție completă este o secvență de litere: S=(l1,l2,…,ln) unde li∈M(di), iar M(di) este
mulțimea literelor asociate cifrei di.

Soluții parțiale
O soluție parțială este o secvență: P=(l1,l2,…,lk),k<n, unde fiecare literă li∈M(di) pentru
1≤i≤k.

Succesorii direcți ai unei soluții parțiale

Fie P=(l1,…,lk), atunci succesorii direcți sunt toate secvențele: P′=(l1,…,lk,lk+1), unde lk+1
∈M(dk+1). Adică, extindem soluția parțială cu fiecare literă posibilă care corespunde cifrei
următoare.

Condiția de viabilitate
O soluție parțială este viabilă dacă:
• Are lungime ≤n
• Fiecare literă li∈M(di)

5. Având un șir de numere întregi distincte candidate și un număr întreg țintă, returnează o listă cu
toate combinațiile unice de candidați în care suma numerelor alese este egală cu ținta. Poți returna
combinațiile în orice ordine. Același număr poate fi ales din candidați de un număr nelimitat de ori.
Două combinații sunt unice dacă cel puțin unul dintre numerele alese este diferit. Cazurile de testare
sunt generate astfel încât numărul de combinații unice care însumează ținta să fie mai mic de 150 de
combinații pentru intrarea dată.

Reprezentarea unei soluții

O soluție completă este o secvență S = (x₁, x₂, ..., xₖ), unde fiecare xᵢ ∈ candidates, iar
x₁ + x₂ + ... + xₖ = target.

Soluții parțiale
O soluție parțială este o secvență P = (x₁, x₂, ..., xᵣ), r ≤ k, în care suma elementelor este mai
mică sau egală cu target.

Succesorii direcți ai unei soluții parțiale

Fie P = (x₁, ..., xᵣ), atunci succesorii direcți sunt toate secvențele P' = (x₁, ..., xᵣ, xᵣ₊₁), unde
xᵣ₊₁ ∈ candidates, și suma elementelor lui P' ≤ target.

Condiția de viabilitate
O soluție parțială este viabilă dacă suma sa este ≤ target. Dacă suma devine mai mare,
abandonăm ramura (backtracking).
6. Având un șir de numere întregi nums cu elemente unice, returnează toate posibilitățile (mulțimea
puterilor). Mulțimea soluțiilor nu trebuie să conțină submulțimi duplicate. Returnează soluția în
orice ordine.

Reprezentarea unei soluții

O soluție completă este o multime S={x1,x2,…,xk},xi∈nums. Soluțiile complete sunt toate
submulțimile posibile ale nums, incluzând:
• mulțimea vidă,
• toate combinațiile de 1 element,
• până la combinația care conține toate elementele din nums.

Soluții parțiale
O soluție parțială este o secvență P=(x1,x2,…,xr), xi∈nums

Succesorii direcți ai unei soluții parțiale

Fie o soluție parțială P=(x1,x2,…,xr), construită din pozițiile i1<i2<…<ir din nums.
Succesorii sunt toate extensiile: P′=(x1,x2,…,xr,xr+1) unde:
• xr+1 este un element din nums, luat de la o poziție ulterioară în nums (pentru a evita
duplicate și a păstra consistența).

Condiția de viabilitate
În acest caz, toate soluțiile parțiale sunt viabile — nu există o restricție care le-ar invalida,
deci nu trebuie să filtrăm decât pentru a evita permutările/duplicarea elementelor deja explorate.

7. Având o grilă de caractere m x n și un șir de caractere cuvânt, returnează true dacă cuvântul există
în grilă. Cuvântul poate fi construit din litere ale celulelor adiacente secvențial, unde celulele
adiacente sunt vecine pe orizontală sau pe verticală. Aceeași celulă cu literă nu poate fi utilizată mai
mult de o dată.

Reprezentarea unei soluții

O soluție completă este o secvență de poziții în grilă: S=((i1,j1),(i2,j2),…,(ik,jk)), unde:
• k=len(word)
• fiecare (it,jt) este o poziție validă în grilă,
• fiecare poziție este adiacentă cu cea precedentă (sus, jos, stânga sau dreapta),
• fiecare poziție apare o singură dată în secvență,
• iar: grid[i1][j1]+grid[i2][j2]+…+grid[ik][jk]=word

Soluții parțiale
O soluție parțială este o secvență: P=((i1,j1),(i2,j2),…,(ir,jr)), r≤k, care formează prefixul:
grid[i1][j1]+…+grid[ir][jr]=word[0:r]

Succesorii direcți ai unei soluții parțiale

Pentru o soluție parțială P=((i1,j1),...,(ir,jr)), succesorii sunt toate pozițiile (ir+1,jr+1)
adiacente ultimei poziții (ir,jr), care:
• sunt în interiorul grilei,
 • nu au fost deja folosite în P,
• și au caracterul potrivit: grid[ir+1][jr+1]=word[r]

Condiția de viabilitate
O soluție parțială este viabilă dacă:
• lungimea ei r≤len(word),
• caracterele din pozițiile selectate formează prefixul: grid[i1][j1]+…+grid[ir][jr]=word[0:r]
Dacă această condiție nu este îndeplinită, ramura se oprește (backtrack).

8. O secvență de coduri gri de n biți este o secvență de 2n numere întregi în care:

• Fiecare număr întreg se află în intervalul [0, 2n – 1],
• Primul număr întreg este 0,
• Un număr întreg apare cel mult o singură dată în secvență,
• Reprezentarea binară a fiecărei perechi de numere întregi adiacente diferă cu exact un bit,
• Reprezentarea binară a primului și ultimului număr întreg diferă cu exact un bit.
Dată fiind o valoare întregă n, returnează orice secvență validă de coduri gri de n biți.

Reprezentarea unei soluții

O soluție completă este un șir de lungime 2^n: S=(x0,x1,…,x2n−1), unde:
• x0=0,
• xi∈[0,2n−1], distinct,
• HammingDistance(xi,xi+1)=1, pentru orice 0≤i<2^(n−2),
• HammingDistance(x2^(n−1),x0)=1 (ciclul închis, dacă se cere).

Soluții parțiale
O soluție parțială este: P=(x0,x1,…,xk) unde:
• x0=0,
• fiecare xi∈[0,2^n−1], distinct,
• xi și xi−1 diferă prin exact un bit.

Succesorii direcți ai unei soluții parțiale

Fie P=(x0,x1,…,xk). Succesorii sunt toți x∈[0,2n−1] care:
• nu sunt deja în P,
• și count_set_bits(x⊕xk)=1 (adică diferă prin 1 bit de ultimul element).

Condiția de viabilitate
O soluție parțială P=(x0,...,xk) este viabilă dacă:
1. Toate elementele sunt distincte.
2. Orice două elemente consecutive xi,xi+1 diferă prin exact un bit.
Pentru o soluție completă, trebuie să se îndeplinească și: count_set_bits(x2n−1⊕x0)=1
9. Un număr aditiv este un șir ale cărui cifre pot forma o secvență aditivă. O secvență aditivă validă
trebuie să conțină cel puțin trei numere. Cu excepția primelor două numere, fiecare număr ulterior
din secvență trebuie să fie suma celor două precedente. Având un șir care conține numai cifre,
returnează true dacă este un număr aditiv sau false în caz contrar.

Reprezentarea unei soluții

O soluție completă este un șir S={s1, s2, s3}, si ∀i≥3,si=si−1+si−2

Soluții parțiale
O soluție parțială este o secvență de numere: P=(s1,s2,…,sr),r<k unde:
• Numerele sunt obținute prin împărțirea prefixului șirului inițial,
• Pentru r≥3, trebuie să se respecte regula aditivă: sr=sr−1+sr−2.

Succesorii direcți ai unei soluții parțiale

Fie P=(s1,…,sr), unde s1∥s2∥…∥sr este un prefix al șirului. Succesorii se obțin prin
adăugarea unui nou număr sr+1, care:
• Este format din următoarele cifre nefolosite din șir,
• Nu începe cu 0 (cu excepția cazului în care este 0),
• Dacă r≥2, atunci sr+1=sr+sr−1.

Condiția de viabilitate
O soluție parțială P=(s1,…,sr) este viabilă dacă:
• Nu conține numere cu zerouri nevalide la început,
• Dacă r≥3, regula aditivă este respectată: si=si−1+si−2 pentru toate i∈[3,r],
• Totalul cifrelor folosite până la sr este un prefix al șirului original.

10. Dat un număr întreg n, returnează numărul total de numere x cu cifre unice, unde 0 ≤ x < 10ⁿ.
Exemplu:
• n = 2 → Cifrele unice în intervalul [0, 99] sunt: 0, 1, 2, ..., 98 fără duplicate ca 11, 22, 33,
etc.

Reprezentarea unei soluții

O soluție completă este o permutare de lungime k (cu k ≤ n) a cifrelor 0..9, care formează
un număr valid: toți sunt distincți daca S=(d1,d2,…,dk), unde toți di sunt distincți,d1!=0 daca k>1.
Acest șir definește un număr x = d₁d₂...dₖ în baza 10, cu x < 10ⁿ.

Soluții parțiale
O soluție parțială este un prefix: P=(d1,d2,…,dr),r<n care respectă:
• Toate cifrele sunt distincte;
• Dacă r>1, d1!=0 (pentru a evita zerouri în față).

Succesorii direcți ai unei soluții parțiale

Fie P=(d1,…,dr) o soluție parțială. Succesorii direcți sunt toate extensiile posibile:
P′=(d1,…,dr,dr+1),unde dr+1∈{0..9}∖{d1,…,dr}
 Condiția de viabilitate
soluție parțială P este viabilă dacă:
• Nu conține cifre duplicate;
• Nu începe cu 0, dacă lungimea este > 1;
• Lungimea sa este ≤ n.

11. Vi se dă un șir de numere întregi nums și o țintă întreagă. Doriți să construiți o expresie din
nums adăugând unul dintre simbolurile „+” și „-” înaintea fiecărui număr întreg din nums și apoi să
concatenați toate numerele întregi. De exemplu, dacă nums = [2, 1], puteți adăuga un „+” înainte de
2 și un „-” înainte de 1 și le puteți concatena pentru a construi expresia „+2-1”. Returnați numărul
de expresii diferite pe care le puteți construi, care evaluează ținta.

Reprezentarea unei soluții

O soluție completă este o secvență de semne asociate fiecărui element din nums:
S=(σ1,σ2,...,σn),σi∈{+,−} care generează expresia:
E=σ1⋅nums[0]+σ2⋅nums[1]+⋯+σn⋅nums[n−1]
Această expresie este validă dacă: E=target

Soluții parțiale
O soluție parțială este o alegere de semne pentru primii k < n termeni:
P=(σ1,…,σk) care definește o sumă parțială: Sk=σ1⋅nums[0]+⋯+σk⋅nums[k−1]

Succesorii direcți ai unei soluții parțiale

Fie P=(σ1,…,σk), atunci succesorii direcți sunt: P′=(σ1,…,σk,σk+1),σk+1∈{+,−}. Adică
adăugăm următorul număr din nums cu semnul + sau -.

Condiția de viabilitate
O soluție parțială este viabilă întotdeauna, deoarece:
• Alegerea semnelor nu duce niciodată la o stare imposibilă (putem aduna sau scădea orice
valoare);
• Dar, putem optimiza: dacă știm că suma parțială este deja mult mai mare (pozitiv sau
negativ) decât target, putem opri recursivitatea devreme pentru eficiență.

12. Să presupunem că aveți n numere întregi etichetate de la 1 la n. O permutare a acestor n numere

întregi perm (indexată de la 1) este considerată o aranjare frumoasă dacă pentru fiecare i (1 <= i <=
n), una dintre următoarele condiții este adevărată:
perm[i] este divizibil cu i.
i este divizibil cu perm[i].
Dată fiind o număr întreg n, returnați numărul de aranjări frumoase pe care le puteți construi.

Reprezentarea unei soluții

O soluție completă este un șir S={s1, s2, …, sn}, si ∀i∈S, (si % i == 0 || i % si == 0)
 Soluții parțiale
O soluție parțială este o secvență de numere: P=(p1,p2,…,pk), k<n unde ∀j∈P,
(pj % j == 0 || j % pj == 0).

Succesorii direcți ai unei soluții parțiale

Succesorii directi ai unei solutii partiale P sunt toate solutii ce adauga un nou numar pk+1
astfel incat (pk+1 % k+1 == 0 || k+1 % pk+1 == 0).

Condiția de viabilitate
În acest caz, toate soluțiile parțiale sunt viabile — nu există o restricție care le-ar invalida.

13. Având un șir S, puteți transforma fiecare literă individual în minusculă sau majusculă pentru a
crea un alt șir. Returnați o listă cu toate șirurile posibile pe care le-am putea crea. Returnați
rezultatul în orice ordine.

Reprezentarea unei soluții

O soluție completă este o permutare P = {p1, p2, …, pn} a sirului S, unde Pi ∈ {A, …, Z}
reunit cu {a, …, z}, cu proprietatile ca:
• daca Si = L, L ∈ {A, …, Z} => Pi = l, l ∈ {a, …, z}
• daca Si = l, l ∈ {a, …, z} => Pi = L, L ∈ {A, …, Z}

Soluții parțiale
O soluție parțială este o secvență de numere: P=(p1,p2,…,pk), k<n unde ∀j∈P, respecta
proprietatile.

Succesorii direcți ai unei soluții parțiale

Fie P=(p1,…,pr) o soluție parțială. Succesorii direcți sunt toate extensiile posibile:
P′=(p’1,…,p’r,p’r+1),unde p’r+1∈{A, …, Z} reunit cu {a, …, z}∖{p1,…,pr}.

Condiția de viabilitate
O solutie partiala P este viabila daca ∀i∈P, i∈A, …, Z} reunit cu {a, …, z} si respecta
proprietatile de la permutare.

14. Vi se dă un șir de cifre num, cum ar fi „123456579”. Îl putem împărți într-o secvență de tip
Fibonacci [123, 456, 579]. Formal, o secvență de tip Fibonacci este o listă f de numere întregi
nenegative astfel încât:

0 <= f[i] < 231, (adică fiecare număr întreg se încadrează într-un tip de număr întreg semnat pe
32 de biți),
[Link] >= 3 și
f[i] + f[i + 1] == f[i + 2] pentru toate 0 <= i < [Link] - 2.

Rețineți că, atunci când împărțiți șirul în bucăți, fiecare bucată nu trebuie să aibă zerouri
suplimentare în față, cu excepția cazului în care bucata este numărul 0 în sine. Returnați orice
secvență de tip Fibonacci împărțită din num sau returnați [] dacă acest lucru nu este posibil.
 Reprezentarea unei solutii
O solutie este o multime S = (s1, s2, …, sn) cu proprietatea ca s[i] = s[i-1] + s[i-2],
n = [Link](), si oricare si este un prefix al sirului nums[0:[Link]()].

Solutie partiala
O solutie partiala este o multime P = (p1, p2, …, pk), k<=n, p[i] = p[i-1] + p[i-2], si oricare
pi este un prefix al sirului nums[o:[Link]()].

Succesorii unei solutii partiale

Succesorii directii ai unei solutii partiale sunt o multime P’ = (p1, p2, …, pk, pk+1), unde
p[k+1] = p[k] + p[k-1]

Conditia de viabilitate
O solutie partiala este viabila daca pentru oricare pi ∈ P, p[i] = p[i-1] + p[i-2] si pi este
prefix al sirului nums[0:[Link]()]

15. Având două numere întregi n și k, returnează un șir de toate numerele întregi de lungime n în
care diferența dintre fiecare două cifre consecutive este k. Poți returna răspunsul în orice ordine.
Reține că numerele întregi nu trebuie să aibă zerouri în față. Numerele întregi precum 02 și 043 nu
sunt permise.

Reprezentarea unei solutii

O solutie este o multime S = (s1, s2, …, sn) cu proprietatea ca s[i].lenght() = n, si
s[i]-s[i-1]=k, si ∈ {1, ..., 9} (nu începe cu 0)

Solutie partiala
O solutie partiala este o multime P = (p1, p2, …, pr), k<=n, p[i].lenght() = n, si
p[i]-p[i-1]=k, pi ∈ {1, ..., 9} (nu începe cu 0)

Succesorii unei solutii partiale

Succesorii directii ai unei solutii partiale sunt o multime P’ = (p1, p2, …, pr, pr+1), unde
p[r+1] - p[r] = k, p[r+1].lenght() = n, pi ∈ {1, ..., 9} (nu începe cu 0)

Conditia de viabilitate
O solutie partiala este viabila daca pentru oricare pi ∈ P, p[i] - p[i-1] = k si [Link]() = n.