Nguồn: CSES

Một thuật toán đơn giản là duyệt qua tất cả các tập con, khi đó độ phức tạp sẽ là ~O(2^n)~. Vì \(2^{40} ≈ 10^{12}\), cách làm này quá chậm. Do đó, ta cần một phương pháp thông minh hơn. Như tên gọi của đề bài, kỹ thuật cần sử dụng ở đây là Meet in the Middle. Với Meet in the Middle, độ phức tạp có thể giảm xuống ~O(n.2^{\frac{n}{2}})~, hoặc thậm chí ~O(2^{\frac{n}{2}})~.

Meet in the Middle là một kỹ thuật khá tổng quát, có thể áp dụng cho nhiều loại bài toán theo những cách khác nhau. Ý tưởng chính là chia bài toán thành hai nửa, giải quyết riêng từng nửa, sau đó kết hợp kết quả của hai nửa để thu được đáp án cuối cùng. Bài toán đếm số tập con có tổng bằng một giá trị cho trước là một ví dụ điển hình có thể áp dụng kỹ thuật này.

Để sử dụng Meet in the Middle, trước tiên ta chia mảng thành hai nửa. Có thể thực hiện đơn giản bằng cách chọn ~\left\lfloor \frac{n}{2} \right\rfloor~ phần tử đầu tiên vào nửa thứ nhất và các phần tử còn lại vào nửa thứ hai.

Sau đó, ta tính và lưu tổng của tất cả các tập con trong từng nửa riêng biệt. Việc này mất ~O(2^{\frac{n}{2}})~ thời gian. Phần còn lại là tìm cách kết hợp thông tin về các tập con để tính số tập con trong mảng ban đầu có tổng bằng ~x~.

Trước tiên, ta sắp xếp hai mảng chứa tổng các tập con. Việc này mất:

~O\left(2^{\frac{n}{2}}.log(2^{\frac{n}{2}})\right)~ ~=~ ~O\left(2^{\frac{n}{2}}.\frac{n}{2}.log2\right)~ ~=~ ~O\left(n.2^{\frac{n}{2}}\right)~

thời gian.

Sau khi hai mảng đã được sắp xếp, ta duyệt mảng thứ nhất theo thứ tự tăng dần. Ta có thể duy trì một con trỏ trên mảng thứ hai và con trỏ này luôn giảm khi ta tiến về phía trước trong mảng thứ nhất. Điều này là do khi phần tử trong mảng thứ nhất tăng lên, phần tử tương ứng trong mảng thứ hai phải giảm xuống để tổng của chúng vẫn bằng ~x~. Vì vậy, thời gian thực hiện bước này là tuyến tính theo độ dài của các mảng, tức ~O\left(2^{\frac{n}{2}}\right)~.

Lưu ý rằng một số tổng của các tập con có thể xuất hiện nhiều lần trong các mảng. Điều này có nghĩa là với mỗi phần tử trong mảng thứ nhất, có thể có nhiều phần tử tương ứng trong mảng thứ hai. Ta xử lý vấn đề này bằng cách xét tất cả các phần tử bằng nhau cùng một lúc.

Như vậy, toàn bộ thuật toán có độ phức tạp:

~O\left(n.2^{\frac{n}{2}} + 2^{\frac{n}{2}}\right)~ ~=~ ~O\left(n.2^{\frac{n}{2}}\right)~.

Với độ phức tạp trên đã đủ để giải quyết bài toán. Ngoài ra, độ phức tạp có thể được cải thiện xuống ~O(2^{\frac{n}{2}})~ nếu sử dụng bảng băm (hash table) thay cho việc sắp xếp các mảng.