Backtracking este o metod de parcurgere sistematic a spaiului soluiilor posibile al unei probleme. Este o metod general de programare, i poate fi adapt pentru orice problem pentru care dorim s obinem toate soluiile posibile, sau s selectm o soluie optim, din mulimea soluiilor posibile. Backtracking este ns i cea mai costisitoare metod din punct de vedere al timpului de execuie.n general vom modela soluia problemei ca un vector v=(v1,v2,v3,...,vn) n care fiecare element vk aparine unei mulimi finite i ordonate Sk, cu k=1,n. n anumite cazuri particulare, mulimile S1 ,S2, S3,...,Sn pot fi identice . Procedm astfel: 1. La fiecare pas k pornim de la o soluie parial v=( v1,v2,v3,...,vk-1) determinat pn n acel moment i ncercm s extindem aceast soluie adugnd un nou element la sfritul vectorului. 2. Cutm n mulimea Sk , un nou element. 3. Dac exist un element neselectat nc, verificm dac acest element ndeplinete condiiile impuse de problem, numite condiii de continuare. 4. Dac sunt respectate condiiile de continuare, adugm elementul soluiei pariale. 5. Verificm dac am obinut o soluie complet. - dac am obinut o soluie complet o afim i se reia algoritmul de la pasul 1. - dac nu am obinut o soluie, k