494.目标和

1. 回溯算法

这题和之前做的那些排列、组合的回溯稍微有些不同，你不需要每次选数据时都是for遍历去选择，很明显这是顺序选择的
比如 数组[0,1]，target=1；

递归数组，每个元素都 + 或者 - ，然后取最后结果为0的即可

class Solution {public int findTargetSumWays(int[] nums, int target) {find(0,nums,target);return count;}private void find(int begin,int[] nums,int target){// 如果减完了，结束if(begin == nums.length){if(target == 0){count++;}return;}target-=nums[begin];find(begin+1,nums,target);target+=nums[begin];target+=nums[begin];find(begin+1,nums,target);target-=nums[begin];   }private int count=0;
}

2. 动态规划

这其实可以抽象为0/1背包问题。
数组中的元素，要么是前面+，要么是前面-，问计算结果为target的方案有多少种。
计算结果为0，即我们把前面为+的元素放在一个集合A中，前面为-的元素放在一个集合B中，二者之差为target即可。
我们如果知道了集合A，那么集合B自然就是数组中剩余元素组成。

可以列个简单的数学公式，假设A集合元素的和为left,B元素和为right，数组总和为sum

left + right = sum;
left - right = target;

二者一相加可以得到 left=(sum+target)/2;
由于都是正整数，left如果不是正整数，说明无解，即没有这种方案。

思路成功转换为，背包容量为left，在数组中找出和刚好为left的方案，并记录方案的最大数。

1. 确定dp[i][j]

即dp[i][j] ：在数组中下标为0～i的元素中任选，和刚好为j的方案数量

2. 确定递推公式
   如果第i个元素不选，那方案数量和dp[i-1][j]的一样
   dp[i][j] = dp[i-1][j]
   如果选了第i个元素，那方案就不仅仅从i-1个元素选出和为j的，从i-1个元素选出和为j-nums[i]的也可以，两种方案数相加。
   dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]]

3. 如何初始化
   dp[0][0]=1 我可以都不选，那方案数就是1
   初始化第一行 dp[0][nums[0]]+=1;
   题目中提示给出nums[i]范围是可能为0，所以如果nums[0]=0,那就是dp[0][0]中都不选的方案中，再添加一种，选择元素0，那就是两个方案了！！！
   重点细节，卡了我一个上午！！！

4. 确定遍历顺序
   先数组元素，再背包容量

5. 模拟推导

class Solution {public int findTargetSumWays(int[] nums, int target) {if(nums.length == 1){return target == nums[0]?1:target == 0-nums[0]?1:0;}// 把集合分成前面放+的正集合和前面放-的负集合.正集合的和为left，负集合的和为right// left+right=sum left-right=target => left = (target+sum)/2// 即转换为问题---把背包容量为left的背包装满有多少种方案// 同时，如果left不为整数，说明不行，返回0// dp[i][j] 在下标0为～i的元素中，填满背包容量为j，有多少种方案// dp[i][j] = dp[i-1][j] 如果不装i// dp[i][j] = Math.max(dp[i-1][j-nums[i]],dp[i-1][j]) 如果装iint sum=0;for(int i:nums){sum += i;}if((target+sum)%2 != 0 ){return 0;}if(target > sum || target < -sum){return 0;}int num = (target+sum)/2;num = num < 0?-num:num;int[][] dp = new int[nums.length][num+1];// 当容量为0的时候，都不选就是一种方案for(int i=0;i<nums.length;i++){dp[i][0]=1;}// 遍历第一行，dp[0][nums[0]]+=1 因为可能第一行中nums[0]=0,此时dp[0][0]其实已经初始化为1了，但是dp[0][0]其实有两个方案的，一个是都不选，一个是选了0，这个细节决定了我们后续的遍历从第二行开始是否成功！！！if(nums[0]<num+1){dp[0][nums[0]]+=1;}for(int i=1;i<nums.length;i++){for(int j=0;j<num+1;j++){dp[i][j] = dp[i-1][j];if(j>=nums[i]){dp[i][j] = dp[i-1][j-nums[i]] + dp[i-1][j];   } }}return dp[nums.length-1][num];}
}

优化成一维的

class Solution {public int findTargetSumWays(int[] nums, int target) {if(nums.length == 1){return target == nums[0]?1:target == 0-nums[0]?1:0;}// 把集合分成前面放+的正集合和前面放-的负集合.正集合的和为left，负集合的和为right// left+right=sum left-right=target => left = (target+sum)/2// 即转换为问题---把背包容量为left的背包装满有多少种方案// 同时，如果left不为整数，说明不行，返回0// dp[i][j] 在下标0为～i的元素中，填满背包容量为j，有多少种方案// dp[i][j] = dp[i-1][j] 如果不装i// dp[i][j] = Math.max(dp[i-1][j-nums[i]],dp[i-1][j]) 如果装iint sum=0;for(int i:nums){sum += i;}if((target+sum)%2 != 0 ){return 0;}if(target > sum || target < -sum){return 0;}int num = (target+sum)/2;num = num < 0?-num:num;int[]dp = new int[num+1];// 当容量为0的时候，都不选就是一种方案dp[0]=1;// 遍历第一行if(nums[0]<num+1){dp[nums[0]]+=1;}for(int i=1;i<nums.length;i++){for(int j=num;j>=nums[i];j--){dp[j] += dp[j-nums[i]]; }}return dp[num];}
}

这道题很经典，建议过段时间重复刷