Este una dintre cele mai cunoscute metode de elaborare a algoritmilor. Ea se aplica acelor probleme in care solutia se poate reprezenta sub forma unui vector x=(x1,. . . , xn)IA1x. . .xAn, unde Ai, i=1, n sunt finite ( i A =ni, i=1, n ). In plus, pentru fiecare problema in parte este necesar ca solutia: x1,...,xn sa satisfaca anumite conditii interne r(x1, . . . , xn).
Multimea A=A1x. . .xAn este spatiul solutiilor posibile. Elementele xIA care satisfac conditiile interne se numesc solutii rezultat. Ne propunem determinarea tuturor solutiilor rezultat, eventual pentru a alege dintre ele pe cea care minimizeaza sau maximizeaza o functie obiectiv.
Metoda Backtracking evita generarea tuturor solutiilor posibile (toate elementele produsului cartezian A1x...xAn). Elementului xkIAk, k=1, n i se atribuie o valoare dupa ce au fost atribuite valori pentru componentele x1IA1,..., xk-1IAk-1. Metoda trece la atribuirea unei valori pentru xk+1IAk+1 doar daca xk impreuna cu x1,...,xk-1 verifica conditiile de continuare, notate rk(x1,...,xk). Daca conditiile rk(x1,...,xk) sunt indeplinite se trece la atribuirea unei valori pentru elementul xk+1IAk+1 al solutiei.
