494. 目标和 回溯法+动态规划
题目
给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
题解
方法一、暴力回溯法
刚刚看到本题的时候，要使用+和-,并且结合非负整数数组来组成目标和。心想这不是一个组合题目嘛，铁定回溯法。来说一下回溯法的基本框架。
解决一个回溯问题，实际上就是一个决策树的遍历过程。一般来说，需要解决三个问题：
路径：也就是已经做出的选择。
选择列表：也就是你当前可以做的选择。
结束条件：也就是到达决策树底层，无法再做选择的条件。
我们所使用的框架基本就是：
LinkedList result = new LinkedList();
public void backtrack(路径，选择列表){
if(满足结束条件){
result.add(结果);
}
for(选择：选择列表){
做出选择;
backtrack(路径，选择列表);
撤销选择;
}
}
其中最关键的点就是：在递归之前做选择，在递归之后撤销选择。
对于本题来讲，相当于在选择nums中的数的情况下，之后再面临两种选择，选择加当前的数，还是选择减当前的数。我们来看具体代码
class Solution {
public List<LinkedList> list = new LinkedList<>();
public int result = 0;
public int findTargetSumWays(int[] nums, int S) {
countCom(nums,0,0,S,new LinkedList<Integer>());
return result;
}
public void countCom(int[] nums, int index,int target,int sum , LinkedList<Integer> trace){
if(trace.size() == nums.length){
if(target == sum) {
list.add(new LinkedList (trace));
result++;
}
return ;
}
//选择列表
for(int i = index; i<nums.length; i++){
//做出+nums[i]
target = target - nums[i];
trace.add(nums[i]);
countCom(nums,i+1,target,sum,trace);
//撤销选择
target = target + nums[i];
trace.removeLast();
//做出-nums[i]
target = target + nums[i];
trace.add(nums[i]);
countCom(nums,i+1,target,sum,trace);
//撤销选择
target = target - nums[i];
trace.removeLast();
}
}
}
思路比较简单，但是由于时间复杂度比较高，Leetcode后台会显示超出时间限制。
方法二、动态规划（背包问题）
虽然上述回溯法超时了，但是依旧给我提供了后续思路，我们仔细观察一下回溯法在这道题的解题框架：
//选择列表
for(int i = index; i<nums.length; i++){
//选择做出+nums[i]
... ...
//选择做出-nums[i]
... ...
}
上述框架叙述了这样一件事，在选择nums[i]这个数的时候，我们该选择+呢？还是选择-呢？还是两种都要算一起呢？写到这思路渐渐明朗起来。这就相当于在背包载重最大为j的情况下，对前i个物品进行选择。这样我们就转换成了背包问题了。
当然，这道题肯定是两种都要算一起，因为我们最后求的是和为目标数 S 的所有添加符号的方法数。
那状态转移方程就出来了。
dp[i][j] = dp[i-1][j+nums[i]] + dp[i-1][j-nums[i]]
解释：j+nums[i]和j-nums[i]表示对nums[i]可以执行加，还可以执行减，那么dp[i][j]的结果值就是加/减之后对应位置的和。
接下来需要明确base case，在本题中这也是关键的一步，很多小伙伴会卡在这里。在这之前我们需要明确状态与选择。对于本题来讲：
状态：即目标和（有范围）
选择：+或- nums数组中的元素
解释：例如，在示例nums = [1, 1, 1, 1, 1]中在非负整数数组的前提下，由于要选择+或者-，那么：
组成的最大和就是对所有元素全选+。sum = 5。
组成的最小和的是对所有元素全选-。sum = -5 。
说明我们的目标和S一定是 -5<= S <=5的，其范围长度length = sum*2 + 1。这样就确定下状态了。那我们的dp表就是:
因为整个状态的范围长度length = sum*2 + 1，而j是从0开始的，故其初始化的位置应为sum。由于状态转移方程为dp[i][j] = dp[i-1][j+nums[i]] + dp[i-1][j-nums[i]].故dp表初始化应为：
if(nums[0] == 0) dp[0][sum] = 2;
else{
dp[0][sum+nums[0]] = 1;
dp[0][sum-nums[0]] = 1;
}
如果nums[0]==0的话，那么+0和-0都应该算作其操作，故if(nums[0] == 0) dp[0][sum] = 2;
具体流程为：
接下就可以写代码了，在写的过程中注意边界的问题即可。
代码
class Solution{
public int findTargetSumWays(int[] nums, int S){
if(nums.length == 0) return 0;
int sum = 0;
for(int i = 0; i < nums.length; i++) sum += nums[i];
if (Math.abs(S) > Math.abs(sum)) return 0;
int[][] dp = new int[nums.length][sum*2+1];
//初始化
if(nums[0] == 0) dp[0][sum] = 2;
else{
dp[0][sum+nums[0]] = 1;
dp[0][sum-nums[0]] = 1;
}
for(int i = 1; i<nums.length; i++){
for(int j = 0; j<(sum*2+1);j++){
int l = (j - nums[i]) >= 0 ? j - nums[i] : 0;
int r = (j + nums[i]) < (sum*2+1) ? j + nums[i] : 0;
dp[i][j] = dp[i-1][l] + dp[i-1][r];
}
}
return dp[nums.length-1][sum+S];
}
}