# 494 - Target Sum

解法一 - DP

目前我們已經對 0/1 背包問題有一定的了解，所以就讓我們來思考一下這題怎麼簡化成我們已知的問題。

我們可以從題目中知道幾件事情：

1. Input array 中所有的 element 必須屬於兩個 subset s1(+), s2(-) 的其中一個

2. 我們要找出所有 sum(s1) - sum(s2) == S 的組合

所以，看到這邊已經有 0/1 背包問題的感覺了，每遇到一個 element，我們都要決定這個 element 要放到 s1 還是 s2，如果是暴力法，那就每一種可能都試試看，然後計算到底有幾種 s1 & s2 滿足 sum(s1) - sum(s2) == S。

不過要寫成 DP 的 recurrence formula，還需要一點巧思。我們可以稍微類比一下 count of subset sum，在 count of subset sum 中，我們要求的是有多少個 subset 的 sum 是 S；所以如果我們可以把這題也變成求類似的解，那就可以用跟 count of subset sum 一樣的解法。

要求類似的解，就等於是只要考慮 sum(s1) == X 就好，只是這個 X 我們還不知道是什麼。sum(s1) - sum(s2) == S 式子裡面比較麻煩的就是 sum(s2)，所以我們現在要想辦法把 sum(s2) 消掉。

讓我們列出兩個 equation:

sum(s1) - sum(s2) == S
sum(s1) + sum(s2) == sum(num)

有上面這兩個 eq，就可以算出

2*sum(s1) == S+sum(num)
=> sum(s1) == (S+sum(num))/2

所以我們就知道剩下的基本上就是一個 subset sum 問題，直接優化成 1D dp array，實作如下：

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int totalSum = 0;
        for(int n:nums)
            totalSum += n;

        if(totalSum < S || ((S+totalSum)%2) != 0)
            return 0;

        return countWays(nums, (S+totalSum)/2);
    }

private:
    int countWays(vector<int>& nums, int target) {
        vector<int> dp(target+1);
        dp[0] = 1;

        for(int i=0; i<nums.size(); i++) {
            for(int s=target; s>=0; s--) {
                if(nums[i] <= s) dp[s] += dp[s-nums[i]];
            }
        }

        return dp[target];

    }
};