class Solution {
private int count;
public int findTargetSumWays(int[] nums, int target) {
this.count = 0;
process(nums,target,0);
return count;
}
public void process(int[] nums, int rest,int index){
if(index == nums.length){
if(rest==0){
count++;
}
return;
}
process(nums,rest-nums[index],index+1);
process(nums,rest+nums[index],index+1);
}
}
这是本题的暴力回溯实现。
但是注意process(nums,rest-nums[index],index+1);这里rest的下一个值是可大可小的所以不能往一个方向去递推。但是所有元素的和是固定的，所给的目标值也是固定的。由下图可以推出，所有带加号的值和带减号的值是固定的。
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for(int i=0; i < nums.length;i++){
sum+=nums[i];
}
// 目标值不能大于总和 目标值可能为负数
if(Math.abs(target)>sum) return 0;
if((target+sum)%2!=0) return 0; // 因为taget是加部分和减部分的和，sum是都是加部分。二者相加，一部分数被算了两遍，除不尽，一定是没合适结果，返回0；
int pos = (sum+target)/2;
int neg = (sum-target)/2;
int capcity = Math.min(pos, neg); // 取pos和neg中的较小者，以使得dp空间最小
int[][] dp = new int[nums.length+1][capcity+1];
// (+或者-)的目标值为0的时候，并且也num也为空的时候，有一个。
dp[0][0] = 1;
for(int i = 1;i <= nums.length;i++){
for(int j = 0; j <= capcity; j++){
if(j<nums[i-1]){
dp[i][j] = dp[i-1][j];
}else{
// i 代表第num中第ige，从一开始算所以取i-1
dp[i][j] = dp[i-1][j]+dp[i-1][j-nums[i-1]];
}
}
}
return dp[nums.length][capcity];
}
}
参考:https://www.bilibili.com/video/BV1o8411j73x/?spm_id_from=333.337.search-card.all.click&vd_source=46d50b5d646b50dcb2a208d3946b1598
作者：flix
链接：https://leetcode.cn/problems/target-sum/solutions/1410230/by-flix-rkb5/