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;
    }
};

LeetCode-494 Target Sum