494. Target Sum Medium
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
Approach
Input: A non-negative integer array nums, an integer target.
Output: Each number can be preceded by + or -, return the number of different expressions that evaluate to target.
This problem belongs to 0-1 Knapsack + Counting DP problems.
This problem has multiple solutions:
- Memoized Recursion (DFS + Cache)
- 2D DP Table Method
- 1D DP (Rolling Array Optimization)
Core Transformation (0-1 Knapsack + Counting DP)
Suppose:
- The sum of all numbers is
s - The sum of all numbers preceded by
+isp
Then the sum of all numbers preceded by - is s - p. The total result required by the problem is p - (s - p) = target.
Simplifying gives:
2p - s = target => p = (s + target) / 2In other words, the problem transforms into:
Pick some numbers from the array such that their sum is
(s + target) // 2. How many ways are there to pick?
This is exactly a typical 0-1 Knapsack problem (each number can only be picked once), and since we care about how many ways, it's Counting DP.
Constraint Checking:
(s + target)must be an even number (otherwise indivisible)p = (s + target) / 2must be a non-negative integer (otherwise no solution)
Solution 1: Memoized Search (Recursion + Cache)
Idea:
- Definition:
dfs(i, c)represents picking some elements from the firstinumbers summing toc. - Transition Equation:
- Do not pick current number:
dfs(i - 1, c) - Pick current number:
dfs(i - 1, c - nums[i])
- Do not pick current number:
- Base Case: when
i < 0, yielding 1 ifc == 0else 0.
Solution 2: 2D DP Table Method (Traditional 0-1 Knapsack)
Idea:
- Definition:
dp[i][j]expresses combination counts selecting from topicomponents scoring exactlyj. - Initialization:
dp[0][0] = 1 - State transitions:
- Don't add current element:
dp[i][j] = dp[i - 1][j] - Append element recursively:
dp[i][j] += dp[i - 1][j - nums[i - 1]]
- Don't add current element:
Solution 3: 1D DP (Space Optimized)
Idea:
- Definition:
dp[c]sums valid configurations accumulating identically toc. - Initialization:
dp[0] = 1 - For every value
x, traverse bottom up checking array components decreasingly fromtargetdown tox:jsdp[c] += dp[c - x] - Sweeping iteratively bottom up prevents using current numbers redundantly mimicking basic 0-1 Knapsack DP syntax.
Implementation
Solution 1: Memoized Search (Recursion + Cache)
from functools import cache
from typing import List
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
total_sum = sum(nums)
# Generating updated total combination tracking needs to be strictly even and positive
new_target = target + total_sum
if new_target < 0 or new_target % 2 == 1:
return 0
# Transforming problem logic determining correct value accumulation sums equating roughly exact middle values
new_target //= 2
n = len(nums)
# Memoization Recursion logic representing choices available picking values equating accurately target tracking subsets
@cache
def dfs(i: int, c: int) -> int:
# If values exhausted verifying completion match
if i < 0:
return 1 if c == 0 else 0
# Discard skipping tracking choice logic
res = dfs(i - 1, c)
# Accept choices adjusting total counts satisfying limitations accurately
if c >= nums[i]:
res += dfs(i - 1, c - nums[i])
return res
return dfs(n - 1, new_target)/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var findTargetSumWays = function(nums, target) {
const sum = nums.reduce((acc, curr) => acc + curr, 0);
let new_target = target + sum;
if (new_target < 0 || new_target % 2 == 1) {
return 0
}
new_target /= 2
const cache = {};
function dfs(i, c) {
if (i < 0) return c == 0 ? 1 : 0;
if (cache[`${i} + ${c}`] != null) return cache[`${i} + ${c}`];
let res = dfs(i - 1, c);
if (c >= nums[i]) {
res += dfs(i - 1, c - nums[i]);
}
cache[`${i} + ${c}`] = res;
return res;
}
return dfs(nums.length - 1, new_target);
};Solution 2: 2D DP Table Method (Traditional 0-1 Knapsack)
from typing import List
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
total = sum(nums)
target += total # Shift calculation resolving subsets satisfying formula accurately
# Validate limitations satisfying accurate target configurations mathematically correctly
if target < 0 or target % 2 == 1:
return 0
target //= 2 # Find combination limits effectively equating sums targeted values
n = len(nums)
# Tracking permutations generating paths combinations reaching constraints effectively
f = [[0] * (target + 1) for _ in range(n + 1)]
f[0][0] = 1 # Formulating initialization 0 choices satisfying zero sum limitations
for i, x in enumerate(nums):
# Evaluate combinations tracking accurately subsets generating targets successfully
for j in range(target + 1):
if j < x:
# Retain values resolving configurations unable holding elements efficiently
f[i + 1][j] = f[i][j]
else:
# Compound combination paths selecting accurate constraints targeting formulas correctly
f[i + 1][j] = f[i][j] + f[i][j - x]
return f[n][target]/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var findTargetSumWays = function(nums, target) {
// Bottom-Up Approach
const sum = nums.reduce((acc, curr) => acc + curr, 0);
let new_target = target + sum;
if (new_target < 0 || new_target % 2 == 1) {
return 0
}
new_target /= 2
const rows = nums.length + 1;
const cols = new_target + 1;
const f = Array.from({length: rows}, () => Array(cols).fill(0));
f[0][0] = 1;
for (let i = 0; i < nums.length; i++) {
for (let j = 0; j < new_target + 1; j++) {
if (j < nums[i]) {
f[i + 1][j] = f[i][j];
} else {
f[i + 1][j] = f[i][j] + f[i][j - nums[i]];
}
}
}
return f[nums.length][new_target];
}Solution 3: 1D DP (Space Optimized)
from typing import List
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
total = sum(nums)
target += total
if target < 0 or target % 2 == 1:
return 0
target //= 2
f = [0] * (target + 1)
f[0] = 1
for x in nums:
# Sweeping iterative combinations effectively iterating backward enforcing unique usages completely constraints limits
for c in range(target, x - 1, -1):
f[c] = f[c] + f[c - x]
return f[target]/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var findTargetSumWays = function(nums, target) {
// Rolling array optimization
const sum = nums.reduce((acc, curr) => acc + curr, 0);
let new_target = target + sum;
if (new_target < 0 || new_target % 2 == 1) {
return 0
}
new_target /= 2
const f = Array(new_target + 1).fill(0);
f[0] = 1;
for (let i = 0; i < nums.length; i++) {
const x = nums[i];
for (let j = new_target; j > x - 1; j--) {
f[j] = f[j] + f[j - nums[i]];
}
}
return f[new_target];
}Complexity Analysis
- Time Complexity:
O(n * target) - Space Complexity:
- Memoized Recursion (DFS + Cache):
O(n * target) - 2D DP Table Method:
O(n * target) - 1D DP (Space Optimized):
O(target)
- Memoized Recursion (DFS + Cache):