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 <= 10001-2：思路idea
Idea is the most important. 首先每一个数字只能选择一次。问一共有多少种组合方法。dp一般可以解决三种问题。
- 最大，最小值
- 存在性
- 计数
首先从数学角度先分析问题。有n个数，添加正负号使其的和为target。假设正数的和是x，负数的和是y，nums的总和为sum，那么我们可以得到一个方程组。
x - y = target. x + y = sum.
解出y = (sum - target)/2，首先y是添负号的数的总和，必须是整数，一定不是小数，所以(sum-target)一定是2的倍数。如果不是，那么一定是无解的。
这边有个小问题，如果说我们选择了一部分数字作为负数和是y，那么其余的数字一定是作为正数和x并且符合题意，每一个数字都不会丢。为什么要想到这个问题，因为下面我们是转换成了0-1背包问题，0-1背包问题是可以自己选择是否装入这个物品。题目说，是每一个数字都得用到，为啥我们还能对每一个数字进行选择，因为我们选择了一部分，另外一部分就自动构成了符合题意的另外一部分。官方的题解并没有讲明这个问题，当然这只是我的猜测，不一定对。
问题就转变成从sum[]数组中选择一部分数字使之和为y，一共有多少种方案<=>从物品中选择一部分物品，使之的总重量为y，一共有多少种方案。
1-3：dp几步曲-
确定状态
由0-1背包的基础可得，dp[i][j]代表从前i个物品中选择物品使之总和为y一共有dp[i][j]种方案。 -
转移方程
对于一个数字有两种。- 选，方案数：dp[i-1][j-nums[i]]
- 不选，方案数：dp[i-1][j]
根据0-1背包得出状态转移方程
dp[i][j]= dp[i-1][j] + dp[i-1][j-nums[i]] -
初始化，处理好边界
对于和为0，从空元素中选择是一种方案，dp[0][0]=1，dp[0][j>=1] = 0 -
确定遍历顺序
根据状态转移方程值的依赖性，从上到下，从左到右进行遍历。
int n = nums.length;
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum < target) {
return 0;
}
// 正整数和是x，负整数的和为y，
// x-y = target，x+y = sum；x=sum-y
// sum-2y = target， y = (sum-target)/2
if ((sum - target) % 2 == 1) {
return 0;
}
int y = (sum - target) / 2;
// 行0~n,列0~y 要想明白为什么是0～n，因为把总和为0不选元素当成了一种方案。第一行，代表，没有元素选出和为j。
// 如果是0～n-1，第一行的dp[][nums[i]] = 2;
int[][] dp = new int[n + 1][y + 1];
//initialization,dp[0][0] = 1, the others is 0
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < y + 1; j++) {
int num = nums[i - 1];
if (j >= num) {
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - num];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n][y];
第一行，代表空元素集中选择数字。数字nums[]作为二维数组的行，在1～n的位置，可以画个表。当然这个数组row范围也能设置成，0~n-1，只要能初始化正确就行，这边第一行针对num[0] 进行初始化比较烦，不如对空元素进行初始化。
1-5：一维数组（滚动数组） int n = nums.length;
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum < target) {
return 0;
}
// 正整数和是x，负整数的和为y，
// x-y = target，x+y = sum；x=sum-y
// sum-2y = target， y = (sum-target)/2
if ((sum - target) % 2 == 1) {
return 0;
}
int y = (sum - target) / 2;
int[] dp = new int[y + 1];
// 就代表无数字的时候，满足和为0，种类数目为1
dp[0] = 1;
// 从第一个数字开始遍历
for (int i = 0; i < n; i++) {
for (int j = y; j >= nums[i]; j--) {
dp[j] += dp[j - nums[i]];
}
// 小于的时候不用修改值，继承上一回的值。
}
return dp[y];
数字在i中从0号开始编号，到n-1。初始化[1,0,0,0…]代表空元素的时候的情况。
