LeetCode-494 Target Sum

Description

给定一个长度为 $n$ 的数组 $a$ ，以及一个整数 $t a r g e t$ 。

数组可以通过+、-符号组成表达式，求表达式结果为 $t a r g e t$ 的方案数。

Constraints

$1 \leq n \leq 20$
$0 \leq a_{i} \leq 1000$
$0 \leq \sum a_{i} \leq 1000$
$- 1000 \leq t a r g e t \leq 1000$

Solution

LeetCode官方给出了 $O (2^{n})$ 的DFS方案和 $O (n \sum a_{i})$ 的01背包方案。

这里展示 $O (n 2^{\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;
    }
};

Link

LeetCode-494 Target Sum