# 0494. Target Sum
Link: https://leetcode.com/problems/target-sum/
###### tags: `Leetcode` `Medium` `FaceBook` `Backtracking` `Dynamic Programming` `Knapsack Problem`
## 思路
### 思路一 Backtracking $O(2^N)$ $O(N)$(depth of the recursion tree)
直接回溯
### 思路二 Backtracking+memo $O(N*t)$ $O(N*t)$ t是所有数之和
回溯 透过memory剪枝
记录在i个位置之后能得到某个数(target-sum)一共有几种走法
### 思路三 DP $O(N*t)$ $O(N*t)$
类似背包问题
只不过从判断每个物品要还是不要变成加上负的还是正的
## Code
### 思路一

class Solution {
    private int ans = 0;
    public int findTargetSumWays(int[] nums, int target) {
        backtracking(nums, target, 0);
        return ans;
    }
    public void backtracking(int[] nums, int target, int idx){
        if(idx==nums.length){
            if(target==0){
                ans++;
            }
            return;
        }
        backtracking(nums, target+nums[idx],idx+1);
        backtracking(nums, target-nums[idx],idx+1);
    }
}

### 思路二

class Solution {
    int total = 0;
    public int findTargetSumWays(int[] nums, int target) {
        total = Arrays.stream(nums).sum();
        
        int[][] memo = new int[nums.length][2*total+1];
        
        for(int[] row : memo){
            Arrays.fill(row, Integer.MIN_VALUE);
        }
        
        return backtracking(nums, target, 0, 0, memo);
    }
    public int backtracking(int[] nums, int target, int idx, int sum, int[][] memo){
        if(idx == nums.length){
            if(sum == target){
                return 1;
            }
            else{
                return 0;
            }
        }
        if(memo[idx][total+sum]!=Integer.MIN_VALUE){
            return memo[idx][sum+total];
        }
        int high = backtracking(nums, target, idx+1, sum+nums[idx],memo);
        int low = backtracking(nums, target, idx+1, sum-nums[idx],memo);
        memo[idx][sum+total] = high+low;
        return memo[idx][sum+total];
    }
}

### 思路三

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int n = nums.length;
        int maxSum = 0;
        for(int i=0; i<n; i++) maxSum += nums[i];
        if(target>maxSum || target<-maxSum) return 0;
        int[][] dp = new int[n][2*maxSum+1];
        dp[0][maxSum+nums[0]]++;
        dp[0][maxSum-nums[0]]++;
        for(int i=1; i<n; i++){
            for(int sum=-maxSum; sum<=maxSum; sum++){
                if(Math.abs(sum-nums[i])<=maxSum) dp[i][sum+maxSum] += dp[i-1][sum+maxSum-nums[i]];
                if(Math.abs(sum+nums[i])<=maxSum) dp[i][sum+maxSum] += dp[i-1][sum+maxSum+nums[i]];
            }
        }
        return dp[n-1][target+maxSum];
    }
}