移动互联网应用的使用情况,惠州百度seo排名,网站建设一般报价多少钱,旅游网页设计论文5000字题目
494. 目标和 给定一个非负整数数组#xff0c;a1, a2, …, an, 和一个目标数#xff0c;S。现在你有两个符号 和 -。对于数组中的任意一个整数#xff0c;你都可以从 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示…题目
494. 目标和 给定一个非负整数数组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位整数存下。
code
func findTargetSumWays(nums []int, S int) int {if len(nums)0 || numsnil{return 0}sum:0for i:0;ilen(nums);i{sumnums[i]}// 1.恒不成立条件1if sum S{return 0}// 2.恒不成立条件2sumSif sum%2!0{return 0}dp:make([]int,sum/21)dp[0]1// 因此只要找到一个子集令它们都取正号并且和等于 (target sum(nums))/2就证明存在解for i:0;ilen(nums);i{for j:sum/2;jnums[i];j--{dp[j]dp[j]dp[j-nums[i]]}}return dp[sum/2]
}
