## [494\. Target Sum](https://leetcode.com/problems/target-sum/)

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

**Constraints:**

- `1 <= nums.length <= 20`
- `0 <= nums[i] <= 1000`
- `0 <= sum(nums[i]) <= 1000`
- `-1000 <= target <= 1000`

2 維 DP

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int n = nums.size();
        // row 是個數，後續的空間優化可以拿掉他，因為我們不需要知道個數
        // map 的 key 是總和，val 是計數 count
        vector<unordered_map<int, int>> dp(n + 1);
        
        // 起始值是 1
        dp[0][0] = 1;
        
        // i 指的是 nums 的 index
        for(int i = 0; i < n; ++i) {
            // 將結果存到 dp 表格中
            for(auto a : dp[i]) {
                int sum = a.first, count = a.second;
                // 對於每個數字我們可以選擇將其加上或減去
                
                // 加法的情況
                dp[i + 1][sum + nums[i]] += count;
                
                // 減法的情況
                dp[i + 1][sum - nums[i]] += count;
            }
        }
        return dp[n][target];        
    }
};

:::success
- 時間複雜度：$O(T \cdot N)$
- 空間複雜度：$O(T \cdot N)$
:::

DP 空間改進

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        unordered_map<int, int> dp;
        // 初始值是 1
        dp[0] = 1;
        for (int num : nums) {
            unordered_map<int, int> t;
            for (auto a : dp) {
                // key 存 sum 的總和
                int sum = a.first, count = a.second;
                // 對於每個數字我們可以選擇將其加上或減去
                // 加法的情況
                t[sum + num] += count;
                // 減法的情況
                t[sum - num] += count;
            }
            dp = t;
        }
        return dp[target];
    }
};

:::success
- 時間複雜度：$O(T \cdot N)$
- 空間複雜度：$O(T)$
:::