Chia Đội Cân Bằng

Lời giải: Chia Đội Cân Bằng

Hướng tiếp cận

Vì chỉ có $12$ người, số cách phân chia hợp lệ nhỏ — có thể duyệt toàn bộ.

Nhận xét quan trọng

1. Số hoán vị của nhãn đội $\{0,0,0,1,1,1,2,2,2,3,3,3\}$ là $\frac{12!}{(3!{)}^4}=369600$. Con số này rất nhỏ.
2. Dùng next_permutation trên mảng nhãn để duyệt tất cả cách gán người vào đội một cách hiệu quả (tự bỏ qua trùng lặp).
3. Có thể tối ưu thêm bằng backtracking với cắt tỉa: nếu hai đội có cùng số người và tổng điểm, chúng là hoán đổi được — bỏ qua.

Thuật toán

Cách 1 — next_permutation (đơn giản):

1. Tạo mảng nhãn $[0,0,0,1,1,1,2,2,2,3,3,3]$.
2. Duyệt tất cả hoán vị duy nhất.
3. Với mỗi hoán vị, tính tổng từng đội và cập nhật đáp án.

Cách 2 — Backtracking với cắt tỉa:

1. Sắp xếp kỹ năng giảm dần.
2. Gán lần lượt từng người vào một trong $4$ đội (mỗi đội tối đa $3$ người).
3. Cắt tỉa: không gán vào đội có cùng trạng thái với đội đã xét trước đó.

Độ phức tạp

• Thời gian: $O\left(\frac{12!}{(3!{)}^4}\right)=O(369600)$
• Bộ nhớ: $O(1)$