LeetCode-494-目标和
# LeetCode-494-目标和
给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示例1：
输入：nums: [1, 1, 1, 1, 1], S: 3
输出：5
解释：
-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
一共有5种方法让最终目标和为3。
提示：
- 数组非空，且长度不会超过 20 。
- 初始的数组的和不会超过 1000 。
- 保证返回的最终结果能被 32 位整数存下。
# 解题思路
方法1、回溯：
每一步选择都有该位置数的正负2种选择方案，画成树状图可以知道需要DFS遍历2棵树
1棵树以第1位数为正开始寻找，1棵树以第1位数为负开始寻找，找到符合要求的答案。
类似于暴力穷举。
当遍历的深度达到数组长度，且路径和等于S的时候，说明找到了一条路径，count++
当不满足路径和要求时，返回上一层，进行回溯，撤销上一次的选择。
方法2、动态规划：
详见https://leetcode-cn.com/problems/target-sum/solution/494-mu-biao-he-by-ming-zhi-shan-you-m9rfkvkdad/
# Java代码1
class Solution {
int res = 0;
int count = 0;
public int findTargetSumWays(int[] nums, int S) {
int len = nums.length;
backtrack(0,nums,S,len);
return count;
}
public void backtrack(int i,int[] nums,int S,int len){
if(i==len){
if(res==S){
count++;
}
return;
}
// 选择正号
res+=nums[i];
backtrack(i+1,nums,S,len);
// 撤销选择
res-=nums[i];
// 选择负号
res-=nums[i];
backtrack(i+1,nums,S,len);
// 撤销选择
res+=nums[i];
}
}
# Java代码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];
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-07-20，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录