题目描述
给定一个正整数数组 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/
解法
方法一
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
if target < -1000 or target > 1000:
return 0
n = len(nums)
dp = [[0] * 2001 for i in range(n)]
dp[0][nums[0] + 1000] += 1
dp[0][-nums[0] + 1000] += 1
for i in range(1, n):
for j in range(-1000, 1001):
if dp[i - 1][j + 1000] > 0:
dp[i][j + nums[i] + 1000] += dp[i - 1][j + 1000]
dp[i][j - nums[i] + 1000] += dp[i - 1][j + 1000]
return dp[n - 1][target + 1000]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | class Solution {
public int findTargetSumWays(int[] nums, int target) {
if (target < -1000 || target > 1000) {
return 0;
}
int n = nums.length;
int[][] dp = new int[n][2001];
dp[0][nums[0] + 1000] += 1;
dp[0][-nums[0] + 1000] += 1;
for (int i = 1; i < n; i++) {
for (int j = -1000; j <= 1000; j++) {
if (dp[i - 1][j + 1000] > 0) {
dp[i][j + nums[i] + 1000] += dp[i - 1][j + 1000];
dp[i][j - nums[i] + 1000] += dp[i - 1][j + 1000];
}
}
}
return dp[n - 1][target + 1000];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int s = 0;
for (int x : nums) s += x;
if (s - target < 0 || (s - target) % 2 != 0) return 0;
target = (s - target) / 2 + 1;
vector<int> dp(target);
dp[0] = 1;
for (int i = 1; i < nums.size() + 1; ++i) {
for (int j = target - 1; j >= nums[i - 1]; --j) {
dp[j] += dp[j - nums[i - 1]];
}
}
return dp[target - 1];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | func findTargetSumWays(nums []int, target int) int {
if target < -1000 || target > 1000 {
return 0
}
n := len(nums)
dp := make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, 2001)
}
dp[0][nums[0]+1000] += 1
dp[0][-nums[0]+1000] += 1
for i := 1; i < n; i++ {
for j := -1000; j <= 1000; j++ {
if dp[i-1][j+1000] > 0 {
dp[i][j+nums[i]+1000] += dp[i-1][j+1000]
dp[i][j-nums[i]+1000] += dp[i-1][j+1000]
}
}
}
return dp[n-1][target+1000]
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | class Solution {
func findTargetSumWays(_ nums: [Int], _ target: Int) -> Int {
if target < -1000 || target > 1000 {
return 0
}
let n = nums.count
var dp = Array(repeating: Array(repeating: 0, count: 2001), count: n)
dp[0][nums[0] + 1000] += 1
dp[0][-nums[0] + 1000] += 1
for i in 1..<n {
for j in -1000...1000 {
if dp[i - 1][j + 1000] > 0 {
dp[i][j + nums[i] + 1000] += dp[i - 1][j + 1000]
dp[i][j - nums[i] + 1000] += dp[i - 1][j + 1000]
}
}
}
return dp[n - 1][target + 1000]
}
}
|
方法二
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
s = sum(nums)
if s - target < 0 or (s - target) % 2 != 0:
return 0
target = (s - target) // 2 + 1
n = len(nums) + 1
dp = [[0] * target for _ in range(n)]
dp[0][0] = 1
for i in range(1, n):
for j in range(target):
dp[i][j] = dp[i - 1][j]
if nums[i - 1] <= j:
dp[i][j] += dp[i - 1][j - nums[i - 1]]
return dp[-1][-1]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | class Solution {
public int findTargetSumWays(int[] nums, int target) {
int s = 0;
for (int x : nums) {
s += x;
}
if (s - target < 0 || (s - target) % 2 != 0) {
return 0;
}
target = (s - target) / 2 + 1;
int[] dp = new int[target];
dp[0] = 1;
for (int i = 1; i < nums.length + 1; ++i) {
for (int j = target - 1; j >= nums[i - 1]; --j) {
dp[j] += dp[j - nums[i - 1]];
}
}
return dp[target - 1];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | func findTargetSumWays(nums []int, target int) int {
s := 0
for _, x := range nums {
s += x
}
if s-target < 0 || (s-target)%2 != 0 {
return 0
}
target = (s-target)/2 + 1
dp := make([]int, target)
dp[0] = 1
for i := 1; i < len(nums)+1; i++ {
for j := target - 1; j >= nums[i-1]; j-- {
dp[j] += dp[j-nums[i-1]]
}
}
return dp[target-1]
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | class Solution {
func findTargetSumWays(_ nums: [Int], _ target: Int) -> Int {
let s = nums.reduce(0, +)
if s - target < 0 || (s - target) % 2 != 0 {
return 0
}
let target = (s - target) / 2
var dp = [Int](repeating: 0, count: target + 1)
dp[0] = 1
for num in nums {
for j in stride(from: target, through: num, by: -1) {
dp[j] += dp[j - num]
}
}
return dp[target]
}
}
|
方法三
方法四