Ý tưởng quay lui và trạng thái

Trong ví dụ mê cung, tại một chỗ rẽ có thể có nhiều hướng. Thử một hướng khả thi để đi tiếp; nếu không tới được đích theo hướng ấy, quay lại chỗ rẽ còn lựa chọn khác để thử. Cần giữ thông tin về trạng thái đang xét và khôi phục phần thay đổi khi quay về. Đây là ý tưởng quay lui (backtracking). Đệ quy diễn tả bước đi tiếp: từ trạng thái hiện tại gọi cùng thủ tục với trạng thái đã mở rộng. Khi lời gọi nhỏ kết thúc, chương trình trở về chỗ gọi và có thể thử lựa chọn kế tiếp. Tìm một nghiệm có thể dừng khi đã thấy; tìm tất cả cần tiếp tục các nhánh còn lại. Hết lựa chọn khả thi ở một trạng thái thì lời gọi ấy kết thúc để trở về mức trước, không phải luôn kết thúc toàn bộ chương trình.

Với bài toán tạo dãy, trạng thái là phần đã chọn, còn gọi là tiền tố. Ban đầu phần này rỗng. Ở bước k, đã chọn k phần tử và đang chọn phần tử kế tiếp. Miền D_k chứa các giá trị có thể dùng cho vị trí k. Từ tiền tố hiện tại, chọn tập S_k các giá trị còn khả thi để mở rộng. Nếu không có giá trị nào thì quay về; nếu đã đủ yêu cầu thì ghi nhận nghiệm. Thứ tự thử trong S_k giúp theo dõi thứ tự kết quả. Với dãy nhị phân không có ràng buộc bổ sung, mỗi vị trí đều chọn 0 hoặc 1, nên S_k vẫn là[0,1]. Quay lui không tự làm số nghiệm ít đi: tìm tất cả dãy dài n vẫn có $2^n$ nghiệm.