Description
给定一个长度为\(n\)的数组\(a\)，以及一个整数\(target\)。
数组可以通过+、-符号组成表达式，求表达式结果为\(target\)的方案数。
Constraints
- \(1 \le n \le 20\)
- \(0 \le a_i \le 1000\)
- \(0 \le \sum a_i \le 1000\)
- \(-1000 \le target \le 1000\)
Solution
LeetCode官方给出了\(O(2^n)\)的DFS方案和\(O(n\sum a_i)\)的01背包方案。
这里展示\(O(n2^{\frac{n}{2}})\)的折半枚举方案。
字面意思，拆成两半去暴力匹配，使得\(2^n\)能降低成\(2^{\frac{n}{2}}\)。
Code
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
if(nums.size() == 1) {
if(nums[0] == target) return 1;
return (-nums[0]) == target;
}
auto bitselect = [](auto &vec, auto f) {
int S = 1 << vec.size();
for(int i = 0, sum = 0; i < S; ++i, sum = 0) {
for(int j = 0; j < vec.size(); ++j) {
if(i >> j & 1) sum += vec[j];
else sum -= vec[j];
}
f(sum);
}
};
unordered_map<int, int> buckets;
int ans = 0;
auto midpoint = nums.begin() + nums.size() / 2;
vector<int> left {nums.begin(), midpoint};
vector<int> right {midpoint, nums.end()};
bitselect(left, [&](int sum) {
buckets[sum]++;
});
bitselect(right, [&](int sum) {
ans += buckets[target - sum];
});
return ans;
}
};