抽签

从大小为n整数集合A中每次抽一个元素x0记录后放回，要求判断抽四次和恰好为m方案是否存在？

测试数据：

– 输入 n=3 A={1,3,5} m=9 输出Yes 因为 1+1+3+5=9所以存在 – 输入 n=3 A={1,3,5} m=5 输出No 因为不存在

方法一：暴力 O(n^4)

bool solve(int n, int m, vector<int> &k) { for (auto a:k) for (auto b:k) for (auto c:k) for (auto d:k) { if (a + b + c + d == m) return true; } return false; }

方法二：优化枚举+二分搜索O(n^2log(n))

bool solve(int n, int m, vector<int> &k) { vector<int> k2; for (size_t i = 0; i < k.size(); i++) for (size_t j = 0; j < k.size(); j++) { k2.push_back(k[i] + k[j]); } sort(k2.begin(), k2.end()); for (size_t i = 0; i < k2.size(); i++) { if (binary_search(k2.begin(), k2.end(), m - k2[i])) return true; } return false; }