Principiul care stă la baza metodei
Principiul care stă la baza metodei backtracking va fi prezentat printr-un exemplu, acela al generării permutărilor. Cum se poate rezolva această problemă?
O primă soluție ar fi să generăm toate elementele produsului cartezian:
{1,2,3}X{1,2,3}X{1,2,3}={11, 12, 13, 21, 22, 23, 31, 32, 33}X{1,2,3}= {111, 112, 113, 121, 122, 123, 131, 132, 133, 211, 212, 213, 221, 222, 223, 231, 232, 233, 311, 312, 313, 321, 322, 323, 331, 332, 333}.
Apoi, urmează să vedem care dintre elementele acestui produs cartezian sunt permutări, adică să conțină numai numere distincte. Astfel, 111,112,... nu sunt permutări, dar 123 este permutare, și așa mai departe. Produsul cartezian are 27 de elemente și dintre ele, doar 6 sunt permutări. În general,din produsul cartezian, sunt doar n! permutări.
Întrebarea este dacă problema nu se poate rezolva eficient? Să observăm că nu are rost să generăm un element al produsului cartezian pentru ca apoi, să ne dăm seama că nu este permutare, deoarece nu este alcătuit din numere distincte. De exemplu, dacă la un pas al algoritmului am generat 22, e clar că nu se poate obține o permutare, oricare ar fi numărul care urmează pe poziția 3.