De multe ori, în aplicaţii apar probleme în care se cere găsirea unor soluţii de forma x=x1x2…xn, unde xi aparţine Ai,
i=1,…,n, în care x1...xn trebuie să îndeplinească anumite condiţii. Am putea să generăm toate combinaţiile posibile de
valori şi apoi să le alegem doar pe cele convenabile.[...]
Rezolvând problema în acest mod, deci generând toate elementele produsului cartezian A1xA2x...xAn şi verificând abia
apoi dacă fiecare combinaţie este o soluţie, eficienţa este scăzută.
Astfel, dacă de exemplu ne propunem să generăm toate cuvintele formate cu literele a, b, c, aşa încât fiecare literă
să apară o singură dată, combinaţiile posibile sunt în număr de 27, dintre care convin doar 6.
Tehnica Backtracking propune generarea soluţiei prin completarea vectorului x în ordinea x1x2...xn şi are la bază un
principiu „de bun simţ”: dacă se constată că având o combinaţie parţială de forma v1v2...vk-1 (unde v1, ..., vk-1 sunt
valori deja fixate), dacă alegem pentru xk o valoare vk şi combinaţia rezultată nu ne permite să ajungem la o soluţie,
se renunţă la această valoare şi se încearcă o alta (dintre cele netestate în această etapă).
Într-adevăr, oricum am alege celelalte valori, dacă una nu corespunde nu putem avea o soluţie.