Algorithm
Problem Name: 494. Target Sum
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'+'before2and a'-'before1and 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
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int findTargetSumWays(int* nums, int numsSize, int S) {
// 1. Backtracking is pretty straightforward, refer to Expression Add Operators.
// 2. 0-1 knapsack dp solution:
int i, T = 0;
int *dp, s, k, n;
for (i = 0; i < numsSize; i ++) {
T += nums[i];
}
if (T < S || ((T + S) & 1)) return 0;
s = (T + S) >> 1;
dp = calloc(s + 1, sizeof(int));
//assert(dp);
dp[0] = 1;
for (i = 0; i < numsSize; i ++) {
n = nums[i];
for (k = s; k >= n; k --) {
dp[k] += dp[k - n];
//printf("%d,%d: %d\n", i, k, dp[k]);
}
}
n = dp[s];
free(dp);
return n;
}
Input
nums = [1,1,1,1,1], target = 3
Output
5
#2 Code Example with C++ Programming
Code -
C++ Programming
// Backtracking
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
int count = 0;
backtrack(nums, S, 0, 0, count);
return count;
}
void backtrack(vector<int>& nums, int S, int sum, int pos, int& count){
if(pos == nums.size()){
if(sum == S) count++;
return;
}
backtrack(nums, S, sum + nums[pos], pos + 1, count);
backtrack(nums, S, sum - nums[pos], pos + 1, count);
}
};
// DP
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
int sum = 0;
for(auto x: nums) sum += x;
if(sum < S || -sum > S) return 0;
vector<int>cur(2 * sum + 1);
vector<int>next(2 * sum + 1);
cur[sum] = 1;
for(int i = 0; i < nums.size(); i++){
for(int j = 0; j < 2 * sum + 1; j++){
if(cur[j] != 0){
next[j + nums[i]] += cur[j];
next[j - nums[i]] += cur[j];
cur[j] = 0;
}
}
swap(cur, next);
}
return cur[sum + S];
}
};
Input
nums = [1,1,1,1,1], target = 3
Output
5
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
int count;
public int findTargetSumWays(int[] nums, int S) {
int[][] dp = new int[nums.length][2001];
for (int[] row : dp) {
Arrays.fill(row, Integer.MIN_VALUE);
}
return calculateWays(nums, 0, 0, S, dp);
}
private void calculateWaysDfs(int[] nums, int idx, int S) {
if (idx == nums.length) {
if (S == 0) {
count++;
}
return;
}
dfs(nums, idx + 1, S - nums[idx]);
dfs(nums, idx + 1, S + nums[idx]);
}
private int calculateWaysDp(int[] nums, int idx, int sum, int S, int[][] dp) {
if (idx == nums.length) {
return sum == S ? 1 : 0;
}
if (dp[idx][sum + 1000] != Integer.MIN_VALUE) {
return dp[idx][sum + 1000];
}
int add = calculateWaysDp(nums, idx + 1, sum + nums[idx], S, dp);
int sub = calculateWaysDp(nums, idx + 1, sum - nums[idx], S, dp);
dp[idx][sum + 1000] = add + sub;
return dp[idx][sum + 1000];
}
}
Input
nums = [1], target = 1
Output
1
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const findTargetSumWays = function(nums, target) {
const sum = nums.reduce((a, b) => a+b);
if(Math.abs(target) > sum) {
return 0;
}
if((target + sum) % 2) {
return 0;
}
const newTarget = (target + sum) / 2;
let dp = new Array(newTarget+1).fill(0);
dp[0] = 1;
for(let i = 0; i < nums.length; i++> {
for(let j = newTarget; j >= nums[i]; j--) {
dp[j] += dp[j - nums[i]];
}
}
return dp[newTarget];
};
Input
nums = [1], target = 1
Output
1
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def findTargetSumWays(self, nums, S):
d = {S:1}
for i in range(len(nums)):
new_d = collections.defaultdict(int)
for k, v in d.items():
new_d[k+nums[i]] += v
new_d[k-nums[i]] += v
d = new_d
return d[0]
Input
nums = [1,1,1,1,1], target = 3
Output
5