### Tóm tắt bài toán
Bài toán yêu cầu kiểm tra xem trong một mảng $A$ cho trước có tồn tại hay không một tập con các phần tử sao cho tổng của chúng bằng $k$.
---
### Hướng giải
Áp dụng ý tưởng của kỹ thuật **Meet in the Middle**, ta chia mảng $A$ thành hai nửa.
Từ đó, xây dựng hai mảng $M$ và $N$, trong đó mỗi mảng lưu tổng của **tất cả các tập con** tương ứng của mỗi nửa sau khi chia.
Tiếp theo, ta duyệt qua từng phần tử $i$ trong $M$ (hoặc $N$) và kiểm tra xem trong mảng còn lại có tồn tại giá trị $k - i$ hay không.
Việc kiểm tra này có thể được thực hiện hiệu quả bằng cách sử dụng **tìm kiếm nhị phân**, hoặc các cấu trúc dữ liệu như `set` hay `map` (trong code tham khảo mình dùng `set`).
**Chú ý**: Do kiểu $A_i\leq10^{18}$ nên ta phải dùng `long long` thay vì `int`
---
### Độ phức tạp
- Việc liệt kê tất cả các tổng tập con của mỗi nửa mảng có độ phức tạp $O\left(2^{\frac{N}{2}}\right)$.
- Ta xét tất cả các phần tử trong một trong hai mảng $M$ hoặc $N$ sẽ mất $O\left(2^{\frac{N}{2}}\right)$ (Do $M$ và $N$ đều có khoảng $2^{\frac{N}{2}}$ phần tử).
- Trong bước kiểm tra, sử dụng tìm kiếm nhị phân, `set` hoặc `map` đều có độ phức tạp $O\left(\frac{N}{2}\right)$.
$\Rightarrow$ Tổng độ phức tạp của thuật toán là $O\left(\frac{N}{2} \times2^{\frac{N}{2}}\right)$, hoàn toàn phù hợp với giới hạn $N \leq 40$.
---
### Code tham khảo
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, k;
vector<int> a;
void f(int idx, int end, vector<int> &b, int cur)
{
if (idx == end)
{
b.push_back(cur);
return;
}
f(idx + 1, end, b, cur);
cur += a[idx];
f(idx + 1, end, b, cur);
}
signed main()
{
cin >> n >> k;
a.resize(n);
for (int i = 0; i < n; i++)
cin >> a[i];
vector<int> one, two;
f(0, n / 2, one, 0);
f(n / 2, n, two, 0);
set<int> st(two.begin(), two.end());
for (int i : one)
if (st.find(k - i) != st.end())
{
cout << "YES\n";
return 0;
}
cout << "NO\n";
}
```
Defylogicguy
Created at
2 likes