# Leetcide 494 - Target sum

`Note:`

- This is also a
`01 knapsack`

problem. - To get the bagWeight, think in this way:
`bagWeight - (sum - bagWeight) = target`

. We pick what’s gonna be`+`

into our bag. - The DP formula is
`DP[j] = DP[j] + DP[j - nums[i]]`

based on two situations when we encounter`nums[i]`

.- When we don’t pick
`nums[i]`

, then it’s still`DP[j]`

as our last iteration. - When we pick
`nums[i]`

, then it’s`DP[j - nums[i]]`

.

- When we don’t pick
- Initialize
`DP[0]`

as`1`

because if it’s`0`

, then all our results would be`0`

.

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 |

1 | /** |