[leetcode]494. Target Sum

Analysis

完了完了 真的要找不到工作了！！！！！苍了天了！！！—— [每天刷题并不难0.0]

You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.
Find out how many ways to assign symbols to make sum of integers equal to target S.

在讨论区看到的一个大神的分析，很强啊！！！链接：
https://leetcode.com/problems/target-sum/discuss/97334/Java-(15-ms)-C%2B%2B-(3-ms)-O(ns)-iterative-DP-solution-using-subset-sum-with-explanation
counter部分主要用了416题的方法：https://blog.****.net/weixin_32135877/article/details/84847236

Implement

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if(sum < S || ((sum+S)&1))
            return 0;
        return counter(nums, (sum+S)>>1);
    }
    int counter(vector<int>& nums, int target){
        vector<int> dp(target+1, 0);
        dp[0] = 1;
        for(int num:nums){
            for(int i=target; i>=num; i--)
                dp[i] += dp[i-num];
        }
        return dp[target];
    }
};