原题
给定一个非负整数数组，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位整数存下。
解法
思想
DFS比较暴力，追求时间快可以用01背包问题的动态规划思想，以后更。
代码
class Solution {
public int[] numsArray;
public int target;
public int findTargetSumWays(int[] nums, int S) {
numsArray = nums;
target = S;
return dfs(0,0);
}
public int dfs(int index,int sum){
if(index == numsArray.length){
if(sum == target) return 1;
else return 0;
}
return dfs(index+1,sum+numsArray[index])+dfs(index+1,sum-numsArray[index]);
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode494-%e7%9b%ae%e6%a0%87%e5%92%8c/
相关推荐
-
leetcode138-复制带随机指针的链表
这道题和leetcode133-克隆图有异曲同工之妙。 原题 给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。 要求返回这个链表的深拷贝。...
-
leetcode76-最小覆盖子串
原题 给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。 示例: 输入: S = "ADOBECODEBANC", T = "ABC" 输...
-
leetcode278-第一个错误的版本
原题 你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。 假...
-
leetcode347-前K个高频元素
原题 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。 示例1： 输入： nums = [1,1,1,2,2,3], k = 2 输出： [1,2] 示例2： 输入： n...
-
leetcode99-恢复二叉搜索树
原题 二叉搜索树中的两个节点被错误地交换。 请在不改变其结构的情况下，恢复这棵树。 示例 1: 输入: [1,3,null,null,2] 1 ...
-
leetcode331-验证二叉树的前序序列化
原题 序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。 _9_ / \ 3 2...
-
leetcode540-有序数组中的单一元素
原题 给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。 示例1: 输入： [1,1,2,3,3,4,4,8,8] 输出： 2 示例2: 输入...
-
leetcode1413-逐步求和得到正数的最小值
原题 给你一个整数数组 nums 。你可以选定任意的 正数 startValue 作为初始值。 你需要从左到右遍历 nums 数组，并将 startValue 依次累加上 nums...
-
leetcode652-寻找重复的子树
原题 给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。 两棵树重复是指它们具有相同的结构以及相同的结点值。 示例1: 1 / \ 2...
-
leetcode456-132模式
原题 给定一个整数序列：a1, a2, ..., an，一个132模式的子序列 ai, aj, ak 被定义为：当 i < j < k 时，ai < ak <...
