Subtask 1: Sinh nhị phân (Brute Force, n ≤ 20)

Duyệt tất cả các tập con của mảng và tìm chênh lệch nhỏ nhất.

Subtask 2: Quy hoạch động (Knapsack DP, n ≤ 1000, tổng ≤ 10^5)

Ý tưởng

• Bài toán tương tự bài toán "Subset Sum", trong đó ta cần tìm một tập con có tổng gần nhất S/2, với S là tổng tất cả các phần tử.
• Đây là bài toán Knapsack 0/1, có thể giải bằng quy hoạch động.

Subtask 3

Nhận xét: Nếu có ~2~ phần tử giống nhau trong mảng, ta có thể chia ~2~ phần tử đó vào ~2~ nhóm mà không làm ảnh hưởng đến kết quả.

Sau khi loại bỏ phần tử lặp, mảng sẽ còn lại tối đa ~2 \times \sqrt{S}~ số với ~S~ là tổng các phần tử trong mảng. Đến đây ta làm như Sub2

Độ phức tạp: O(~n \times \sqrt{n}~)