\(Firega\) và \(Tenshi\) thường xuyên tham gia các cuộc thi lập trình và họ đều thích sự cân bằng trong danh tính của họ. Một ngày, \(Tenshi\) đặt ra một thách thức cho \(Firega\): “Hãy viết một chương trình để kiểm tra xem một tập hợp các số có thể được chia thành hai phần có tổng bằng nhau hay không.” \(Firega\) thấy thách thức khá thú vị và đồng ý tham gia. Hãy giúp \(Firega\) giải quyết bài toán này.
Yêu cầu:
Viết một chương trình nhận vào một tập hợp các số và kiểm tra xem tập hợp đó có thể được chia thành hai phần có tổng bằng nhau hay không. Nếu có, in ra \(YES\), ngược lại in ra \(NO\).
Dữ liệu vào Specification:
-
Dòng đầu tiên chứa một số nguyên \(n (1 \le n \le 125)\), là số phần tử trong tập hợp.
-
Dòng thứ hai chứa n số nguyên \(a_1, a_2,..., a_n\) \((-1000 \le a_i \le 1000)\), là giá trị của các phần tử trong tập hợp.
Dữ liệu ra Specification:
- Một dòng duy nhất, in ra \(YES\) nếu tập hợp có thể được chia thành hai phần có tổng bằng nhau, ngược lại in ra \(NO\).
Ví dụ:
| INPUT | OUTPUT | Giải thích |
|---|---|---|
| 6 7 2 7 4 2 0 |
YES | Tập hợp có thể được chia thành hai phần: \({7, 2, 2}\) và \({7, 4, 0}\), có tổng bằng nhau là \(11\). |
| 4 1 2 3 7 |
NO | Không có cách chia tập hợp thành hai phần có tổng bằng nhau. |
Ràng buộc:
- \(43 \%\) Test đầu có \(0 \lt n \le 50, 0 \le a_i \le500\).
- \(29 \%\) Test tiếp có \(50 \le n \le 100, 0 \le a_i \le 750\).
- \(15 \%\) Test nữa có \(100 \lt n \le 125,500 \le a_i \le 1000\).
- \(13 \%\) Test cuối không giới hạn gì thêm.