###### tags: `Leetcode` `medium` `dynamic programming` `python` `c++`

# 494. Target Sum

## [題目連結:] https://leetcode.com/problems/target-sum/description/

## 題目:
You are given an integer array ```nums``` and an integer ```target```.

You want to build an **expression** out of nums by adding one of the symbols ```'+'``` and ```'-'``` before each integer in nums and then concatenate all the integers.

* For example, if ```nums = [2, 1]```, you can add a ```'+'``` before ```2``` and a ```'-'``` before ```1``` and concatenate them to build the expression ```"+2-1"```.

Return the number of different **expressions** that you can build, which evaluates to ```target```.

**Example 1:**

Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3.
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

**Example 2:**

Input: nums = [1], target = 1
Output: 1

## 解題想法:
* 給定一個數組與一個target number，對於此數組每個數天加'+'、'-'，使其求和為target number，求滿足的組合數

* 使用DP:
* 定義dp[i][j]: **到第i個數和為j的組合數**
* (nums: 0~i-1，第i個數字為nums[i-1])
* dp[i][j]=case1+case2:
* **Case1:**
* **dp[i-1][j-nums[i-1]]**
* 使用前i-1個數字，可構成j-nums[i-1]
* 則加上nums[i-1] (+第i個數字)即可為j
* **Case2:**
* **dp[i-1][j+nums[i-1]]**
* 使用前i-1個數字，可構成j+nums[i-1]
* 則減掉nums[i] (-第i個數字)即可為j
* 對於初始dp:
* max_sum=sum(nums)
* **dp=[[0 for _ in range(2*max_sum+1)] for _ in range(len(nums)+1)]**
* 因為範圍可以為(-max_sum)至(+max_sum)
* 所以取0~ 2 * max_sum+1
* 初始
* dp[0][0]=1: 使用0個數總和為0，1種組合
* pos_0=max_sum: **總和為0的位置在中間**

## Python:

class Solution(object):
    def findTargetSumWays(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        #dp[i][j]:到第i個數(nums: 0~i-1，第i個數字為nums[i-1]) 和為j的組合數
        max_sum=sum(nums)
        if max_sum<target:
            return 0
        #dp m:len(nums)+1  n:位置從-max_sum~0~+max_sum
        dp=[[0 for _ in range(2*max_sum+1)] for _ in range(len(nums)+1)]
        pos_0=max_sum #和為0的位置在中間
        dp[0][pos_0]=1 #初始: 用0個數和為0 總共一種
        for i in range(1, len(nums)+1):
            for j in range(2*max_sum+1):
                #使用前i-1個數字 可構成j+nums[i-1]: 則-nums[i](-第i個數字)即可為j
                dp[i][j]+=dp[i-1][j+nums[i-1]] if j+nums[i-1]<2*max_sum+1 else 0
                #使用前i-1個數字 可構成j-nums[i-1]: 則+nums[i-1](+第i個數字)即可為j
                dp[i][j]+=dp[i-1][j-nums[i-1]] if j-nums[i-1]>=0 else 0
        return dp[len(nums)][target+pos_0]

* 上述缺點為浪費記憶體空間
* ex: nums=[100], targert=200
* dp要準備200個空間太浪費了
* 可以用hash table存
* 或者改用dfs遍歷而非dp (網路大神蠻多dfs解的~但尚未研究)

## C++:
* 二維陣列可以用**vector<unordered_map<int, int>>**
* dp[i][j]=value

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int n=nums.size();
        vector<unordered_map<int, int>> dp(n+1);
        dp[0][0]=1;
        for (int i=1; i<n+1; i++){
            //當前要求dp[i]，需要由dp[i-1]往推算
            for (auto &j: dp[i-1]){
                int curSum=j.first, count=j.second;
                dp[i][curSum-nums[i-1]]+=count;
                dp[i][curSum+nums[i-1]]+=count;
            }
        }
        return dp[n][target];
    }
};