## Algorithm

Problem Name: 494. 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`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
int findTargetSumWays(int* nums, int numsSize, int S) {
// 1. Backtracking is pretty straightforward, refer to Expression Add Operators.
// 2. 0-1 knapsack dp solution:
int i, T = 0;
int *dp, s, k, n;

for (i = 0; i  <  numsSize; i ++) {
T += nums[i];
}

if (T  <  S || ((T + S) & 1)) return 0;

s = (T + S) >> 1;
dp = calloc(s + 1, sizeof(int));
//assert(dp);

dp[0] = 1;
for (i = 0; i  <  numsSize; i ++) {
n = nums[i];
for (k = s; k >= n; k --) {
dp[k] += dp[k - n];
//printf("%d,%d: %d\n", i, k, dp[k]);
}
}

n = dp[s];

free(dp);

return n;
}
``````
Copy The Code &

Input

cmd
nums = [1,1,1,1,1], target = 3

Output

cmd
5

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
// Backtracking
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
int count = 0;
backtrack(nums, S, 0, 0, count);
return count;
}

void backtrack(vector<int>& nums, int S, int sum, int pos, int& count){
if(pos == nums.size()){
if(sum == S) count++;
return;
}
backtrack(nums, S, sum + nums[pos], pos + 1, count);
backtrack(nums, S, sum - nums[pos], pos + 1, count);
}
};

// DP
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
int sum = 0;
for(auto x: nums) sum += x;
if(sum  <  S || -sum > S) return 0;
vector<int>cur(2 * sum + 1);
vector<int>next(2 * sum + 1);
cur[sum] = 1;
for(int i = 0; i  <  nums.size(); i++){
for(int j = 0; j  <  2 * sum + 1; j++){
if(cur[j] != 0){
next[j + nums[i]] += cur[j];
next[j - nums[i]] += cur[j];
cur[j] = 0;
}
}
swap(cur, next);
}
return cur[sum + S];
}
};
``````
Copy The Code &

Input

cmd
nums = [1,1,1,1,1], target = 3

Output

cmd
5

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
int count;
public int findTargetSumWays(int[] nums, int S) {
int[][] dp = new int[nums.length][2001];
for (int[] row : dp) {
Arrays.fill(row, Integer.MIN_VALUE);
}
return calculateWays(nums, 0, 0, S, dp);
}

private void calculateWaysDfs(int[] nums, int idx, int S) {
if (idx == nums.length) {
if (S == 0) {
count++;
}
return;
}
dfs(nums, idx + 1, S - nums[idx]);
dfs(nums, idx + 1, S + nums[idx]);
}

private int calculateWaysDp(int[] nums, int idx, int sum, int S, int[][] dp) {
if (idx == nums.length) {
return sum == S ? 1 : 0;
}
if (dp[idx][sum + 1000] != Integer.MIN_VALUE) {
return dp[idx][sum + 1000];
}
int add = calculateWaysDp(nums, idx + 1, sum + nums[idx], S, dp);
int sub = calculateWaysDp(nums, idx + 1, sum - nums[idx], S, dp);
dp[idx][sum + 1000] = add + sub;
return dp[idx][sum + 1000];
}
}
``````
Copy The Code &

Input

cmd
nums = [1], target = 1

Output

cmd
1

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const findTargetSumWays = function(nums, target) {
const sum = nums.reduce((a, b) => a+b);
if(Math.abs(target) > sum) {
return 0;
}
if((target + sum) % 2) {
return 0;
}
const newTarget = (target + sum) / 2;
let dp = new Array(newTarget+1).fill(0);
dp[0] = 1;
for(let i = 0; i < nums.length; i++> {
for(let j = newTarget; j >= nums[i]; j--) {
dp[j] += dp[j - nums[i]];
}
}
return dp[newTarget];
};
``````
Copy The Code &

Input

cmd
nums = [1], target = 1

Output

cmd
1

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def findTargetSumWays(self, nums, S):
d = {S:1}
for i in range(len(nums)):
new_d = collections.defaultdict(int)
for k, v in d.items():
new_d[k+nums[i]] += v
new_d[k-nums[i]] += v
d = new_d
return d[0]
``````
Copy The Code &

Input

cmd
nums = [1,1,1,1,1], target = 3

Output

cmd
5