494. Target Sum

可以用dfs, 簡單, 但很慢

class Solution {
public:
    void dfs(vector<int> &nums, int cur, int start, int &target, int &res){
        if(start == nums.size()){
            if(target == cur){
                res++;
            }
            return;
        }
        dfs(nums, cur + nums[start], start + 1, target, res);
        dfs(nums, cur - nums[start], start + 1, target, res);
    }
    int findTargetSumWays(vector<int>& nums, int target) {
        int res = 0;
        dfs(nums, 0, 0, target, res);
        return res;
    }
};

接著有一種dp的作法

從還沒開始選開始, dp hashtable 0為1,

接著, dp[0] = 1, 從頭開始, 隨著遍布每個值, dp[sum- target] 和 dp[sum + target], sum 為到目前為止的所有可能, count為這個sum的次數, 所以 sum+target, 與 sum - target自然就再加上這個count

最後找到target的index即可

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        unordered_map<int, int> dp;
        dp[0] = 1;
        for(int i = 0; i < nums.size();i++){
            unordered_map<int, int> tmp;
            for(auto a: dp){
                int sum = a.first;
                int cnt = a.second;
                tmp[sum + nums[i]]+=cnt;
                tmp[sum - nums[i]]+=cnt;
            }
            dp = tmp;
        }
        return dp[target];
        
    }
};