Cách tiếp cận Brute Force (chậm)

Duyệt tất cả các cặp ~(i, j)~ với ~j \subseteq i~:

for i in 0..2^M-1:
    for j in 0..2^M-1:
        if (i & j) == j: g[i] += f[j]

Độ phức tạp ~O(4^M)~ hoặc ~O(3^M)~ nếu chỉ duyệt submask. Không đủ nhanh với ~M = 20~.

SOS DP - Ý tưởng cốt lõi

Quan sát: ~j \subseteq i~ khi và chỉ khi ~j~ khác ~i~ ở đúng các bit mà ~i~ có giá trị ~1~.

Ta xử lý từng bit một. Sau lần lặp thứ ~k~, ~g[i]~ = tổng ~f[j]~ với mọi ~j~ thỏa mãn:

• Các bit từ ~0~ đến ~k-1~ của ~j~ có thể là ~0~ hoặc bằng bit tương ứng của ~i~.
• Các bit từ ~k~ trở lên của ~j~ bằng ~i~.

Thuật toán

g = f[:]
for i in range(M):       # duyệt từng bit
    for mask in range(1<<M):
        if mask >> i & 1:    # bit i của mask = 1
            g[mask] += g[mask ^ (1<<i)]

Độ phức tạp

• Thời gian: ~O(M \times 2^M)~ — với ~M = 20~: ~\approx 20 \times 10^6 = 2 \times 10^7~
• Bộ nhớ: ~O(2^M)~

Ứng dụng

SOS DP được dùng rộng rãi trong lập trình thi đấu: bitmask DP, bài toán AND/OR convolution, đếm tập con thỏa điều kiện, v.v.