前言

今天這題也是top 100 liked的題目─494. Target Sum。雖然是medium，但我覺得很難QQ 一開始寫的dfs雖然過了，但頗沒有效率，花了非常久的時間想去弄懂官方解答跟各種神人的dp解，就來一起看看吧！

想法

這題我的第一個想法是先把題目變單純一點，用目前的sum去減去target，獲得的東西/2就變成了任選幾個elements組成新的sum的題目，而我這個算法新的sum代表是任選幾個把他們的符號變成-的。若把目前的(sum+target)/2，這個就是任選幾個前面的符號變成+的題目。
依此概念，我寫出了一個dfs解，不過頗沒有效率，還有待研究優化方式，如下：
概念說明：排序後從第一個開始選，去後面dfs確認任選後面不同的結果是否可達到sum

class Solution {
public:
    void helper(vector<int>& nums, int target, int k, int &ans){
        if(target==0){
            ++ans;
        }
        for(int i=k;i<nums.size();++i){
            if(target<nums[k]){
                return;
            }
            helper(nums, target-nums[i], i+1, ans);
        }
    }
    
    int findTargetSumWays(vector<int>& nums, int target) {
        // turn the problem to unsigned target sum
        // compute the sum 
        int sum=0;
        for(int i=0;i<nums.size();++i){
            sum+=nums[i];
        }
        int targetNew = (sum-target)/2;
        if ((sum-target)%2!=0){
            return 0;
        }
       
        // use DFS to search for answer
        sort(nums.begin(),nums.end());
        int ans=0;
        helper(nums, targetNew, 0, ans);
        
        return ans;

    }
};

不過重點是來研究dp解到底要怎麼做呢？
我們先從比較可以理解的2維DP開始看。
首先跟前面一樣先算出new target，採用(sum+target)/2的方式來算需要取哪幾個元素為+。
而重點是DP的遞迴，用二維的table來記錄，一維是從~第i個nums挑選，nums[0:i]的組合，第二維是加總為多少，裡面存的值就是有幾種組合。初始就是二維為0的都是1，就是什麼都不選。開始更新就從i只有一個開始，j直接從0開始，到new target為止。然後從開始去找要不要加這個數，加了nums[i]之後代表每個nums[i-1][j]次數=nums[i-1][j-nums[i]]+nums[i-1][j]，後面代表不加。
程式碼如下：

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        // compute the nums sum to avoid some impossible cases and compute for new target
        int sum = accumulate(nums.begin() , nums.end() , 0);
        // cut down on some impossible answers
        // not enough or always too big or not possible 
        if(sum<target || -sum>target || (sum+target)%2!=0){
            return 0;
        }       
        // all should be used => trap!! if there are 0s, there are multiple answers
        //if(sum==target || sum==-target){
        //    return 1;
        //}
        // compute for how much the positive sums should be (-negative sum=target)
        int targetNew = (target + sum)/2;
        // use 2d dp[i][j] to save the nums[0:i] sums to j counts
        vector<vector<int>> dp(nums.size()+1,vector<int>(targetNew+1,0));
        // i=0, j=0 => not choosing any elements and the sum is 0
        dp[0][0] = 1;
        //for(int i=0;i<nums.size();++i){
        //    dp[i][0]=1;
        //}
        
        for(int i=1;i<=nums.size();++i){
            // for every sum, update its count
            for(int j=0;j<=targetNew;++j){
                //cout<<i<<j<<endl;
                // nums[i] chosen count + not chosen count
                if((j-nums[i-1])>=0){
                    dp[i][j] = dp[i-1][j-nums[i-1]] + dp[i-1][j];
                }else{
                    dp[i][j] = dp[i-1][j];
                }
                
            }
        }
        return dp[nums.size()][targetNew];
        
    }
};

還可以優化為1維的DP來節省空間，但先理解到這裡為止吧XD

結語

sum系列真的非常多，又經典又有挑戰性，就繼續sum系列吧！