题目
题目
思路
回溯
n个数共有种添加符号的方法，使用回溯遍历所有的表达式，回溯过程中维护一个计数器count，记录遇到结果为target的次数。
class Solution {
int count = 0;
public int findTargetSumWays(int[] nums, int target) {
backTrack(nums, target, 0, 0);
return count;
}
public void bakcTrack(int[] nums, int target, int index, int sum) {
if (index == nums.length) {
if (sum == target) {
count++;
}
} else {
backTrack(nums, target, index + 1, sum + nums[index]);
backTrack(nums, target, index + 1, sum - nums[index]);
}
}
}
动态规划
- 原问题等同于：
找到nums一个正子集P和一个负子集N，使得总和等于target。即sum(P) - sum(N) == target，
即sum(P) + sum(N) + sum(P) - sum(N) == target + sum(P) + sum(N)
即2 * sum(P) == target + sum(nums)， 其中target + sum(nums)必须>=0且为偶数，否则等式不可能成立。
则问题转换为：存在多少个子集P，使sum(P) == (target + sum(nums))/2。
或者sum(N) == (sum(nums) - target)/2 -
数据结构：
边界条件：
dp[i][j]表示前i个元素有多少个目标和为j的子集。
边界条件
- dp[i][j] = dp[i - 1][j]
- 如果nums[0...i - 1]存在和为j - nums[i]的子集，则dp[i][j] += dp[i - 1][j - nums[i]]
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for (int num : nums) {
sum += num;
}
int diff = sum - target;
if (diff < 0 || diff % 2 != 0) {
// 0 或奇数
return 0;
}
int n = nums.length;
int neg = diff / 2;
// 数组默认初始值为0
int[][] dp = new int[n + 1][neg + 1];
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
int num = nums[i - 1];
for (int j = 0; j <= neg; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= num) {
dp[i][j] += dp[i - 1][j - num];
}
}
}
return dp[n][neg];
}
}
