递归解法

递归解法，开始解法存在超时，优化方法是将vector的长度放在类成员中或通过参数传递，如果在helper中每次求nums.size()会导致运行超时。

class Solution {
private:
    //目标和个数
    int count;
    //vector大小,减少递归函数里查询O(n)复杂度
    int size;
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        size = nums.size();
        helper(nums,0,0,S);
        return count;
    }
private:
    void helper(const vector<int>& nums,int len,int sum,int S){
        if(len == size)
        {
            if(sum == S)
                count++;
            return;
        }else{
            helper(nums,len+1,sum+nums[len],S);
            helper(nums,len+1,sum-nums[len],S);
        }
    }
};

运行效率:

Runtime: 1120 ms, faster than 19.53% of C++ online submissions for Target Sum.
Memory Usage: 8.9 MB, less than 98.13% of C++ online submissions for Target Sum.

递归加记忆化

递归之所以执行效率比较低是因为存在大量的重复计算，所以可以使用记忆化来解决这个问题。

class Solution {
private:
    int target;
    int vec_size;
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        target = S;
        vec_size = nums.size();
        vector<unordered_map<int,int>> mem(nums.size());
        return helper(nums,0,0,mem);
    }
private:
    int helper(const vector<int> & nums,int loc,int sum,vector<unordered_map<int,int>> &mem) {
        if(loc == vec_size)
            return sum == target;
        auto iter = mem[loc].find(sum);
        if(iter != mem[loc].end()) return iter->second;
        mem[loc][sum] = helper(nums,loc+1,sum+nums[loc],mem) + helper(nums,loc+1,sum-nums[loc],mem);
        return mem[loc][sum];
    }
};

运行效率:

Runtime: 216 ms, faster than 36.79% of C++ online submissions for Target Sum.
Memory Usage: 61.2 MB, less than 9.71% of C++ online submissions for Target Sum.

动态规划解法

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        unordered_map<int,int> cur{{0,1}},next;
        for(int i = 0;i < nums.size();i++)
        {
            for(auto& it : cur)
            {
                next[it.first + nums[i]] += it.second;
                next[it.first - nums[i]] += it.second;
            }
            swap(cur,next);
            next.clear();
        }
        
        return cur[S];
    }
};

运行效率:

Runtime: 140 ms, faster than 45.56% of C++ online submissions for Target Sum.
Memory Usage: 35.4 MB, less than 30.00% of C++ online submissions for Target Sum.

这里的dp解法与之前的解法不同，这里向后递推不是线性关系，比如我知道了dp[n]，可以求解dp[n+1]，这道题的解法我理解由初始状态向后扩展，以官方例子Input: nums is [1, 1, 1, 1, 1], S is 3.为例：

cur = 0 next 1 -1
---------
cur = -1 next 0 -2
cur = 1 next 2 0
---------
cur = 2 next 3 1
cur = 0 next 1 -1
cur = -2 next -1 -3
---------
cur = -3 next -2 -4
cur = -1 next 0 -2
cur = 1 next 2 0
cur = 3 next 4 2
---------
cur = 0 next 1 -1
cur = 2 next 3 1
cur = -4 next -3 -5
cur = 4 next 5 3
cur = -2 next -1 -3
---------

开始时我们只知道{0,1},然后+1 和-1，这样我们就知道了要组成1和-1需要的组合个数，接着对1和-1同样加上当前当前元素nums[i],这个例子中比较特殊所有元素都是1，每次swap(cur,next),然后清空掉next.