Bài toán liệt kê

Trong thực tế, có một số bài toán yêu cầu chỉ rõ: trong một tập các đối tượng cho trước có bao

nhiêu đối tượng thoả mãn những điều kiện nhất định. Bài toán đó gọi là bài toán đếm cấu hình tổ

hợp.

Trong lóp các bài toán đếm, có những bài toán còn yêu cầu chỉ rõ những cấu hình tìm được thoả

mãn điều kiện đã cho là những cấu hình nào. Bài toán yêu cầu đưa ra danh sách các cấu hình có thể

có gọi là bài toán liệt kê tố họp.

Để giải bài toán liệt kê, cần phải xác định được một thuật toán để có thể theo đó lần lượt xây dựng

được tất cả các cấu hình đang quan tâm. Có nhiều phương pháp liệt kê, nhưng chúng cần phải đáp

ứng được hai yêu cầu dưới đây:

• Không được lặp lại một cấu hình

• Không được bỏ sót một cấu hình