给定一个正整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 ‘+’ 或 ‘-‘ ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-‘ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 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
+1 + 1 + 1 + 1 – 1 = 3
本题有两种思路来解决问题：
- 使用回溯算法
每个元素都可以加 + 或者 加 -，所以每个数字有两种状态可以选择，一共有n个数字，也就是有 2^n 中选择的方法。对应到回溯搜索树上就是一颗完全的二叉搜索树。可以想象一下选择结果。
所以，可以使用回溯把所有子集结果选出来，判断哪些子集和为target即可。 - 转换为背包问题使用动态规划
我们假设sum为数组之和，neg为加上 – 号元素的之和，所以
sum – neg – neg = target（neg是正的），所以问题就转换成
neg = (sum – target) / 2 ,从数组中选出几个数之和为neg，这样的背包问题，与上一道题：分割等和子集 一摸一样。
func findTargetSumWays(nums []int, target int) int {
var count int = 0
dfs(0,target,len(nums),0,&nums,&count)
return count
}
func dfs(cur int, target int, length int, sum int, nums *[]int, count *int) {
if cur == length {
if target == sum {
*count++
}
return
}
sum += (*nums)[cur]
dfs(cur + 1, target, length, sum, nums, count)
sum -= (*nums)[cur]
sum -= (*nums)[cur]
dfs(cur + 1, target, length, sum, nums, count)
sum += (*nums)[cur]
}
动态规划(这个有一点问题,没来得及调)：
func findTargetSumWays(nums []int, target int) int {
var sum int
for _, num := range(nums) {
sum += num
}
if (sum - target) % 2 != 0 {
return 0
}
var neg = (sum - target) / 2
var dp[][]int
for i := 0; i < len(nums) + 1; i++ {
ar := make([]int, neg + 1)
dp = append(dp, ar)
}
dp[0][0] = 1
for j := 1; j < neg + 1; j++ {
dp[0][j] = 0
}
for i := 1; i < len(nums) + 1; i++ {
for j := 0; j < neg + 1; j++ {
if j < nums[i - 1] {
dp[i][j] = dp[i - 1][j]
} else {
dp[i][j] = dp[i - 1][j]
dp[i][j] += dp[i][j - nums[i - 1]]
fmt.Println(dp[i][j])
temp := dp[i - 1][j]
temp2 := dp[i][j - nums[i - 1]]
temp3 := temp + temp2
fmt.Println(temp)
fmt.Println(temp2 == dp[i][j - nums[i - 1]])
fmt.Println(temp3)
fmt.Println(i)
fmt.Println(j)
fmt.Println(dp[i - 1][j])
fmt.Println(dp[i][j - nums[i - 1]])
fmt.Println(dp[i][j])
}
}
}
return dp[len(nums)][neg]
}
func dfs(cur int, target int, length int, sum int, nums *[]int, count *int) {
if cur == length {
if target == sum {
*count++
}
return
}
sum += (*nums)[cur]
dfs(cur + 1, target, length, sum, nums, count)
sum -= (*nums)[cur]
sum -= (*nums)[cur]
dfs(cur + 1, target, length, sum, nums, count)
sum += (*nums)[cur]
}
Original: https://blog.csdn.net/weixin_44627672/article/details/127806714
Author: 爱喝咖啡的Tomcat
Title: 【leetcode】加减的目标值
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/658010/
转载文章受原作者版权保护。转载请注明原作者出处！