# LC 494. Target Sum

### [Problem link](https://leetcode.com/problems/target-sum/)

###### tags: `leedcode` `python` `c++` `medium` `DP`

You are given an integer array <code>nums</code> and an integer <code>target</code>.

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

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

Return the number of different **expressions** that you can build, which evaluates to <code>target</code>.

**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:**

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

## Solution 1 - DP
#### Python

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        if abs(target) > sum(nums) or (sum(nums) + target) % 2:
            return 0

        bagSize = (sum(nums) + target) // 2
        dp = [0] * (bagSize + 1)
        dp[0] = 1

        for i in range(len(nums)):
            for j in range(bagSize, nums[i] - 1, -1):
                dp[j] += dp[j - nums[i]]
        
        return dp[-1]
    

#### C++

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if ((target + sum) % 2) {
            return 0;
        }
        /*
        * let bagSize = subSum of nums, then, sum of nums can split to bagSize and sum - bagSize.
        * => target = bagSize - (sum - bagSize)
        * => bagSize = (target + sum) / 2
        */
        int bagSize = (target + sum) / 2;
        if (bagSize < 0) {
            return 0;
        }
        vector<int> dp(bagSize + 1, 0);
        dp[0] = 1;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = bagSize; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp.back();
    }
};

>### Complexity
>m = bagSize
>n = nums.length
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(mn) | O(m) |

## Note
sol1:
1.

if ((target + sum) % 2) {
    return 0;
}

如果target 與 sum 相差1, 則永遠不可能達成題目要求.

2.
與一般01背包不同, 這次是求裝滿背包有幾種方法而不是背包最多能裝多重.
dp公式變為

dp[j] += dp[j - nums[i]];

[ref](https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0494.%E7%9B%AE%E6%A0%87%E5%92%8C.md)