Thuật toán tìm các tập hợp con của tập n phần tử cho trước

[ihere]

Mình có thể làm bài này bằng cách viết các chuỗi nhị phân liên tiếp, nhưng chỉ với 20 phần tử thì chương trình chạy như con rùa. Bạn có biết tên thuật toán nào, hoặc có thể gửi lên đây cho mình được không? Mình cần thuật toán chạy được với khoảng 100 (hoặc hơn) phần tử là được!

[noname.cpp]

Chậm là đúng thôi, bởi vì số tập con của 1 tập có 20 phần tử đã là 2^20 ( hơn 1 triệu). Để liệt kê 1 triệu phần tử bằng cách in ra màn hình hay ghi ra tệp cũng đều rất mất nhiều thời gian cho dù thuật toán có rất nhanh.

Còn nếu bạn định liệt kê số tập con của 1 tập có 100 phần tử thì số lượng của chúng là 2^100=1,23*10^30 thì không biết bạn có đủ kiên nhẫn để đợi không. Để liệt kê một tập con cần một chuỗi 100bit, máy tính của tôi có một ổ cứng dung lượng 80GB = 64*10^10 bit. Vậy để liệt kê toàn bộ số tập con này cần 100*2^100 / (64*10^10) xấp xỉ 200 tỉ tỉ cái ổ cứng 80GB.