Trong các kĩ thuật cơ bản thiết kế thuật toán, quay lui là một trong các kĩ thuật quan trọng nhất. Nó có thể được áp dụng để tìm ra một nghiệm hoặc tất cả các nghiệm của bài toán.
Tư tưởng của phương pháp quay lui là như sau:
- Ta xây dựng vectơ nghiệm dần từng bước, bắt đầu từ véc tơ không.
- Thành phần đầu tiên được chọn ra từ tập S1=A1.
- Khi đã chọn được các thành phần x1,...,xi-1 thì từ các điều kiện của bài toán ta sẽ xác định được tập Si các ứng cử viên có thể chọn làm thành phần xi.Tập Si là tập con của Ai và phụ thuộc vào các thành phần x1,x2,...,xi-1 đã chọn. Chọn một phần tử xi từ Si ta mở rộng nghiệm một phần (x1,x2,...,xi-1) đến nghiệm một phần (x1,x2,...,xi0. Lặp lại quá trình trên để tiếp tục mở rộng nghiệm 1 phần (x1,x2,...,xi0. Nếu không thể chọn được thành phần xi+1 thì quay lại chọn một phần tử khác của Si làm xi.