Elearning CodePath – CTP Online Judge

Chia mảng thành hai phần có tổng bằng nhau

HASH002

🟢 Hard #Prefix Sum #Hash #Dynamic Programming #Interval

Cho dãy số nguyên $A = (A_1, A_2, \dots, A_N)$.

Hãy đếm số cách chia toàn bộ các phần tử của mảng thành hai nhóm rời nhau, mỗi phần tử thuộc đúng một nhóm, và tổng của hai nhóm bằng nhau.

Lưu ý: tính cả các cách chia đối xứng. Nếu $(I, J)$ là một cách hợp lệ thì $(J, I)$ cũng được tính là một cách.

Dữ liệu vào

| Thành phần | Mô tả |
|---|---|
| Dòng 1 | Số nguyên dương $N$ |
| Dòng 2 | $N$ số nguyên $A_1, A_2, \dots, A_N$ |

Ràng buộc

| Thành phần | Giới hạn |
|---|---|
| $1 \le N \le 40$ | |
| $-10^9 \le A_i \le 10^9$ | |

Kết quả ra

| Thành phần | Mô tả |
|---|---|
| Gồm 1 dòng | In ra số cách chia có thứ tự $(I, J)$ sao cho tổng hai nhóm bằng nhau |

Ví dụ

| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| `4`<br>`1 2 1 2` | `4` | Tổng toàn mảng là $6$, nên mỗi nhóm phải có tổng $3$. <br>Có 2 cách chia không xét thứ tự là $\{A_1,A_2\};\{A_3,A_4\}$ và $\{A_1,A_4\};\{A_2,A_3\}$. Vì tính cả thứ tự nên có $4$ cách. |

Subtask

| Subtask | Ràng buộc | Tỷ lệ điểm |
|---|---|---|
| 1 | $1 \le N \le 20$ | 30% |
| 2 | $21 \le N \le 30$ | 30% |
| 3 | $31 \le N \le 40$ | 40% |

✅ Đã AC: 4 / 20 submissions