Tập hợp cân bằng

Lời giải: Tập hợp cân bằng

Hướng tiếp cận

Gặp nhau ở giữa (Meet in the middle): chia $N$ bò thành 2 nửa, liệt kê tất cả tập con của mỗi nửa.

Nhận xét quan trọng

1. Tập con $S$ cân bằng ↔ tổng $T={\sum }_{i\in S}{M}_i$ chẵn và tồn tại tập con $A\subseteq S$ với ${\sum }_{i\in A}{M}_i=T/2$.
2. Chia bò thành nửa trái (H bò) và nửa phải (H2 bò). Với mỗi cặp $(lmask,rmask)$: cần tồn tại $sub\_l\subseteq lmask$ và $sub\_r\subseteq rmask$ sao cho $\text{lsum}[sub\_l]+\text{rsum}[sub\_r]=T/2$.
3. Tiền xử lý: với mỗi $lmask$, tính tập hợp $\{lsum[sub\_l]:sub\_l\subseteq lmask\}$ (sắp xếp để tìm kiếm nhị phân).

Thuật toán

1. Với mỗi $lmask$ ($2^{N/2}$ giá trị): liệt kê tất cả $sub\_l\subseteq lmask$, lưu lsum vào mảng sắp xếp.
2. Với mỗi $(lmask,rmask)$: nếu $T$ lẻ → bỏ qua. Với mỗi $sub\_r\subseteq rmask$, tìm kiếm nhị phân $T/2-rsum[sub\_r]$ trong mảng của $lmask$.

Độ phức tạp

• Thời gian: $O(2^{N/2}·3^{N/2})$ — chấp nhận được với $N\le 20$.
• Bộ nhớ: $O(3^{N/2})$