# LeetCode Target Sum

LeetCode Target Sum

You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols `+` and `-`. For each integer, you should choose one from `+` and `-` as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Example 1:

```Input: nums is [1, 1, 1, 1, 1], S is 3.
Output: 5
Explanation:

-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

There are 5 ways to assign symbols to make the sum of nums be target 3.
```

Note:

1. The length of the given array is positive and will not exceed 20.
2. The sum of elements in the given array will not exceed 1000.
3. Your output answer is guaranteed to be fitted in a 32-bit integer.

```class Solution {
private:
void dfs(vector<int>& nums, int step, int S, int& ans) {
if (step == nums.size() && S == 0) {
++ans;
return;
}
if (step == nums.size())return;
dfs(nums, step + 1, S - nums[step], ans);
dfs(nums, step + 1, S + nums[step], ans);
}
public:
int findTargetSumWays(vector<int>& nums, int S) {
int ans = 0;
dfs(nums, 0, S, ans);
return ans;
}
};
```

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

DP的代码如下：

```class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
int n = nums.size(), sum = 0;
for (int i = 0; i < n; ++i)sum += nums[i];
if (S<-sum || S>sum)return 0;
//if (S == -sum || S == sum)return 1; // nums={1,0},S=1; 1=1+0=1-0
vector<vector<int>> dp(n + 1, vector<int>(2 * sum + 1, 0));
dp[0][sum] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < 2 * sum + 1; ++j) {
//考虑第i个数字是+还是-
//i从1开始，所以第i个数字的下标是i-1
if (j >= nums[i - 1])dp[i][j] += dp[i - 1][j - nums[i - 1]];
if (j + nums[i - 1] < 2 * sum + 1)dp[i][j] += dp[i - 1][j + nums[i - 1]];
}
}
return dp[n][S + sum];
}
};
```

DP的问题一般都可以优化空间，比如上述代码可以用两个数组互相滚动赋值来代替n+1个数组。

```class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
int n = nums.size(), sum = 0;
for (int i = 0; i < n; ++i)sum += nums[i];
if (S<-sum || S>sum)return 0;
vector<vector<int>> dp(2, vector<int>(2 * sum + 1, 0));
int i = 0, pre = (i & 1) ? 1 : 0, cur = (i & 1) ? 0 : 1;
dp[pre][sum] = 1; // 取0个数字，加和为0的方案有1种。把和0偏移到sum位置
while (i < n) {
pre = (i & 1) ? 1 : 0;
cur = (i & 1) ? 0 : 1;
for (int j = 0; j < 2 * sum + 1; ++j) {
if (dp[pre][j] != 0) {
if (j + nums[i] < 2 * sum + 1)dp[cur][j + nums[i]] += dp[pre][j]; // 在j的基础上加nums[i]
if (j - nums[i] >= 0)dp[cur][j - nums[i]] += dp[pre][j]; // 在j的基础上减nums[i]
}
}
fill(dp[pre].begin(), dp[pre].end(), 0); // 清空pre数组，因为下一轮pre要用作cur数组
++i;
}
return dp[cur][S + sum];
}
};
```

## One thought on “LeetCode Target Sum”

1. Pingback: LeetCode Target Sum | nce3xin_code