class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
}
};
剑指 Offer II 102. 加减的目标值
给定一个正整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
示例 1：
输入：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
示例 2：
输入：nums = [1], target = 1 输出：1
提示：
1 <= nums.length <= 200 <= nums[i] <= 10000 <= sum(nums[i]) <= 1000-1000 <= target <= 1000
注意：本题与主站 494 题相同： https://leetcode.cn/problems/target-sum/
原站题解
python3 解法, 执行用时: 64 ms, 内存消耗: 14.9 MB, 提交时间: 2022-11-22 15:37:23
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
_s = sum(nums)
diff = _s - target
if diff < 0 or diff % 2 == 1: return 0
neg = diff // 2
dp = [1] + [0] * neg
for num in nums:
for j in range(neg, num-1, -1):
dp[j] += dp[j-num]
return dp[neg]
golang 解法, 执行用时: 0 ms, 内存消耗: 6.3 MB, 提交时间: 2022-11-22 15:32:10
func findTargetSumWays(nums []int, target int) int {
sum := 0
for _, v := range nums {
sum += v
}
diff := sum - target
if diff < 0 || diff%2 == 1 {
return 0
}
n, neg := len(nums), diff/2
// dp[i][j]: 从数组nums的前i个数中选元素, 使其和等于j的方案数
dp := make([][]int, n+1)
for i := range dp {
dp[i] = make([]int, neg+1)
}
dp[0][0] = 1
for i, num := range nums {
for j := 0; j <= neg; j++ {
dp[i+1][j] = dp[i][j]
if j >= num {
dp[i+1][j] += dp[i][j-num]
}
}
}
return dp[n][neg]
}
golang 解法, 执行用时: 600 ms, 内存消耗: 2 MB, 提交时间: 2022-11-22 15:28:26
func findTargetSumWays(nums []int, target int) (count int) {
var backtrack func(int, int)
backtrack = func(index, sum int) {
if index == len(nums) {
if sum == target {
count++
}
return
}
backtrack(index+1, sum+nums[index])
backtrack(index+1, sum-nums[index])
}
backtrack(0, 0)
return
}
golang 解法, 执行用时: 0 ms, 内存消耗: 2.3 MB, 提交时间: 2022-11-22 15:24:45
func findTargetSumWays(nums []int, target int) int {
sum := 0
for _, v := range nums {
sum += v
}
diff := sum - target
if diff < 0 || diff%2 == 1 {
return 0
}
neg := diff/2
dp := make([]int, neg+1)
dp[0] = 1
for _, num := range nums {
for j := neg; j >= num; j-- {
dp[j] += dp[j-num]
}
}
return dp[neg]
}