Description#
You are given an integer array nums and an integer target.
You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.
- For example, if
nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1".
Return the number of different expressions that you can build, which evaluates to target.
Example 1:
Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 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
Example 2:
Input: nums = [1], target = 1
Output: 1
Constraints:
1 <= nums.length <= 200 <= nums[i] <= 10000 <= sum(nums[i]) <= 1000-1000 <= target <= 1000
Solutions#
Solution 1#
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:
s = sum(nums)
if s < target or (s - target) % 2 != 0:
return 0
m, n = len(nums), (s - target) // 2
dp = [[0] * (n + 1) for _ in range(m + 1)]
dp[0][0] = 1
for i in range(1, m + 1):
for j in range(n + 1):
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
21
22
23
24
| class Solution {
public int findTargetSumWays(int[] nums, int target) {
int s = 0;
for (int v : nums) {
s += v;
}
if (s < target || (s - target) % 2 != 0) {
return 0;
}
int m = nums.length;
int n = (s - target) / 2;
int[][] dp = new int[m + 1][n + 1];
dp[0][0] = 1;
for (int i = 1; i <= m; ++i) {
for (int j = 0; j <= n; ++j) {
dp[i][j] = dp[i - 1][j];
if (nums[i - 1] <= j) {
dp[i][j] += dp[i - 1][j - nums[i - 1]];
}
}
}
return dp[m][n];
}
}
|
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 = accumulate(nums.begin(), nums.end(), 0);
if (s < target || (s - target) % 2 != 0) return 0;
int m = nums.size(), n = (s - target) / 2;
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
dp[0][0] = 1;
for (int i = 1; i <= m; ++i) {
for (int j = 0; j <= n; ++j) {
dp[i][j] += dp[i - 1][j];
if (nums[i - 1] <= j) dp[i][j] += dp[i - 1][j - nums[i - 1]];
}
}
return dp[m][n];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| func findTargetSumWays(nums []int, target int) int {
s := 0
for _, v := range nums {
s += v
}
if s < target || (s-target)%2 != 0 {
return 0
}
m, n := len(nums), (s-target)/2
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
}
dp[0][0] = 1
for i := 1; i <= m; i++ {
for j := 0; j <= n; j++ {
dp[i][j] = dp[i-1][j]
if nums[i-1] <= j {
dp[i][j] += dp[i-1][j-nums[i-1]]
}
}
}
return dp[m][n]
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| impl Solution {
#[allow(dead_code)]
pub fn find_target_sum_ways(nums: Vec<i32>, target: i32) -> i32 {
let mut sum = 0;
for e in &nums {
sum += *e;
}
// -x + (sum - x) = target <-> -2 * x + sum = target <-> 2 * x = sum - target
if sum < target || (sum - target) % 2 != 0 {
// There is no way to get any expression in this case
return 0;
}
let n = nums.len();
let m = (sum - target) / 2;
let mut dp: Vec<Vec<i32>> = vec![vec![0; m as usize + 1]; n + 1];
// Initialize the dp vector
dp[0][0] = 1;
// Begin the actual dp phase
for i in 1..=n {
for j in 0..=m as usize {
// nums[i - 1] is not included
dp[i][j] = dp[i - 1][j];
if nums[i - 1] <= (j as i32) {
// nums[i - 1] is included
dp[i][j] += dp[i - 1][j - (nums[i - 1] as usize)];
}
}
}
dp[n][m as usize]
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| /**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var findTargetSumWays = function (nums, target) {
let s = 0;
for (let v of nums) {
s += v;
}
if (s < target || (s - target) % 2 != 0) {
return 0;
}
const m = nums.length;
const n = (s - target) / 2;
let dp = new Array(n + 1).fill(0);
dp[0] = 1;
for (let i = 1; i <= m; ++i) {
for (let j = n; j >= nums[i - 1]; --j) {
dp[j] += dp[j - nums[i - 1]];
}
}
return dp[n];
};
|
Solution 2#
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
s = sum(nums)
if s < target or (s - target) % 2 != 0:
return 0
n = (s - target) // 2
dp = [0] * (n + 1)
dp[0] = 1
for v in nums:
for j in range(n, v - 1, -1):
dp[j] += dp[j - v]
return dp[-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 v : nums) {
s += v;
}
if (s < target || (s - target) % 2 != 0) {
return 0;
}
int n = (s - target) / 2;
int[] dp = new int[n + 1];
dp[0] = 1;
for (int v : nums) {
for (int j = n; j >= v; --j) {
dp[j] += dp[j - v];
}
}
return dp[n];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int s = accumulate(nums.begin(), nums.end(), 0);
if (s < target || (s - target) % 2 != 0) return 0;
int n = (s - target) / 2;
vector<int> dp(n + 1);
dp[0] = 1;
for (int& v : nums)
for (int j = n; j >= v; --j)
dp[j] += dp[j - v];
return dp[n];
}
};
|
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 _, v := range nums {
s += v
}
if s < target || (s-target)%2 != 0 {
return 0
}
n := (s - target) / 2
dp := make([]int, n+1)
dp[0] = 1
for _, v := range nums {
for j := n; j >= v; j-- {
dp[j] += dp[j-v]
}
}
return dp[n]
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| impl Solution {
#[allow(dead_code)]
pub fn find_target_sum_ways(nums: Vec<i32>, target: i32) -> i32 {
let mut sum = 0;
for e in &nums {
sum += *e;
}
if sum < target || (sum - target) % 2 != 0 {
// Just directly return
return 0;
}
let n = ((sum - target) / 2) as usize;
let mut dp: Vec<i32> = vec![0; n + 1];
// Initialize the dp vector
dp[0] = 1;
// Begin the actual dp phase
for e in &nums {
for i in (*e as usize..=n).rev() {
dp[i] += dp[i - (*e as usize)];
}
}
dp[n]
}
}
|
Solution 3#
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
@cache
def dfs(i, t):
if i == n:
if t == target:
return 1
return 0
return dfs(i + 1, t + nums[i]) + dfs(i + 1, t - nums[i])
ans, n = 0, len(nums)
return dfs(0, 0)
|
