// Latihan bergaya OSN, Bab 13, soal 3 -- pembahasan. // // bisa[s] = benar kalau jumlah s bisa dibentuk dari barang yang sudah // diproses. Perulangan jumlah berjalan mundur supaya satu barang tidak // dipakai dua kali. #include #include using namespace std; int main() { int n; cin >> n; vector w(n); int total = 0; for (int i = 0; i < n; i++) { cin >> w[i]; total += w[i]; } if (total % 2 != 0) { cout << "TIDAK\n"; return 0; } int separuh = total / 2; vector bisa(separuh + 1, false); bisa[0] = true; for (int i = 0; i < n; i++) { for (int s = separuh; s >= w[i]; s--) { if (bisa[s - w[i]]) bisa[s] = true; } } if (bisa[separuh]) cout << "YA\n"; else cout << "TIDAK\n"; return 0; }