建站公司技术服务费,山西时代网站建设,网站的题目,做网站含营销给定一个非负整数数组#xff0c;a1, a2, ..., an, 和一个目标数#xff0c;S。现在你有两个符号 和 -。对于数组中的任意一个整数#xff0c;你都可以从 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示例 1:
输入: nums…给定一个非负整数数组a1, a2, ..., an, 和一个目标数S。现在你有两个符号 和 -。对于数组中的任意一个整数你都可以从 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示例 1:
输入: nums: [1, 1, 1, 1, 1], S: 3 输出: 5 解释:
-11111 3 1-1111 3 11-111 3 111-11 3 1111-1 3
一共有5种方法让最终目标和为3。 注意:
数组非空且长度不会超过20。 初始的数组的和不会超过1000。 保证返回的最终结果能被32位整数存下。
思路
每一个位置都有正负两个选择依次递归找出所有的可能最后结果与目标值S相同的情况有多少就是有多少种方法 tips一开始把count写成了全局的静态变量可能是提交系统不认可count一直是0 。。。。。。
提交的代码
class Solution { int count 0; public void fun(int nums[],int sum,int S,int i) { if(inums.length) { if(sumS) { count; } return; } fun(nums,sumnums[i],S,i1); fun(nums,sum-nums[i],S,i1); } public int findTargetSumWays(int[] nums, int S) { fun(nums,nums[0],S,1); fun(nums,-nums[0],S,1); return count; }
}
