494. Target Sum
Problem Description
You're given a list of numbers called nums
and a single number called target
. Your task is to form a mathematical expression by adding either a '+' (plus sign) or a '-' (minus sign) before each number in nums
, then concatenate (join together) these numbers with their signs to form an expression. The end goal is to find out how many different expressions you can create that, once evaluated, equal the target
.
For instance, if nums
is [2, 1]
and your target
is 1, you could create the expression "+2-1", which equals 1. You want to find out all such possible expressions that result in the target
.
Here's what you need to consider:
- You can only use '+' or '-' before each number.
- You can't reorder the numbers – their order in the expression must match their order in the given
nums
list. - The objective is to count the number of valid expressions, not necessarily to generate each one.
Flowchart Walkthrough
Let's use the algorithm flowchart to deduce the right approach for solving LeetCode 494. Target Sum. You can follow along using the Flowchart. Here's a step-by-step walkthrough:
-
Is it a graph?
- No: The problem is about achieving a target sum using numbers in an array, not about nodes and edges as in graph problems.
-
Need to solve for kth smallest/largest?
- No: The problem is not about finding the kth smallest or largest element, but about finding ways to reach a target sum.
-
Involves Linked Lists?
- No: The problem involves arrays, not linked lists.
-
Does the problem have small constraints?
- Yes: The problem can have constraints small enough that allows considering all subsets of the numbers.
-
Brute force / Backtracking?
- Yes: The problem requires exploring multiple combinations to find the number of ways to achieve the target sum, making brute force and backtracking suitable methods.
Conclusion: Based on the flowchart analysis, using a backtracking approach is suggested for solving the problem by exploring various combinations to achieve the target sum. This ensures that all potential solutions are considered.
Intuition
Understanding the problem, we see that it resembles a classic problem in computer science known as the subset sum problem, except it allows for both positive and negative summations. The crux is to figure out how to partition nums
into two subsets where the difference between the sums of the subsets equals target
.
First step is to notice a helpful fact: if we sum all numbers with a '+' and then subtract the sum of numbers with a '-', we should obtain the target
. This is basically the same as finding two subsets with a particular sum difference.
Now, how do we solve this with dynamic programming? We can use a technique similar to the 0-1 Knapsack problem. The idea is to iteratively build up an array dp
where each index represents a possible sum of numbers, starting from 0 up to some value that depends on nums
and target
. Each cell in dp
will tell us the number of ways to achieve that sum.
But how do we compute the size of dp
and its initial values? We define a new variable n
which is the sum that we want one subset to have so that the other subset has a sum of n + target
(given that the total sum of nums
is s
). It turns out n
should be (s - target) / 2
. We only proceed if s - target
is even, otherwise, it's not possible to split nums
into two such subsets.
Once we have dp
setup starting at dp[0] = 1
(there's one way to achieve a sum of 0: by choosing no numbers), we start populating dp
by iterating through each number in nums
. For each v
in nums
, we iterate backwards through dp
from n
down to v
(since v
is the smallest sum that including v
can achieve) and update dp[j]
to include the number of ways we can achieve the sum j - v
.
In the end, dp[n]
gives us the number of different expressions we can form that equal target
.
The code provided implements this dynamic programming approach efficiently.
Learn more about Dynamic Programming and Backtracking patterns.
Solution Approach
The provided solution uses a dynamic programming approach to solve the problem efficiently, much like the "0-1 Knapsack" problem. The solution involves some pre-processing steps and then iteratively filling out a dp
array to count the number of ways to reach different sums.
Here's a step-by-step breakdown of the implementation:
-
Calculate the sum
s
of all numbers innums
. This is done to determine the sum of one subset (n
) so that the difference with the other subset's sum will betarget
. -
Check for two conditions that might make it impossible to create expressions equal to
target
:- If the total sum
s
is less thantarget
, it's not possible to create any expression equal totarget
. - If
s - target
is odd, we can't split the array into two subsets with integer sums that have the needed difference.
- If the total sum
-
Initialize the
dp
array of sizen + 1
with zeros and setdp[0]
to 1 – this signifies that there is one way to create a sum of zero (by choosing no numbers). -
Iterate over each number
v
innums
. For eachv
, iterate backwards over thedp
array fromn
down tov
to avoid recomputing values that rely on the current index. This is crucial because we must not count any combination twice. -
Update the
dp[j]
value by adding the number of combinations that exist without the current numberv
(dp[j - v]
). This step accumulates the number of ways there are to achieve a sum ofj
by either including or excluding the current numberv
.
By the end of the iteration, dp[-1]
(which is dp[n]
) will hold the number of possible expressions that can be created using nums
to equal the target
.
Example of dp
Array Update
Here’s a hypothetical example to illustrate the dynamic programming update process:
-
Suppose
nums
=[1,2,3]
andtarget
=1
. We computen = (s - target) / 2
, which would be2
in this case. -
Our
dp
array is[1, 0, 0, 0, 0]
initially. -
During the iteration process:
- When
v
=1
, we updatedp
to[1, 1, 0, 0, 0]
. - When
v
=2
, we updatedp
forj
from2
to1
, resulting in[1, 1, 1, 0, 0]
. - When
v
=3
, we updatedp
forj
from2
to1
, but this time there are no changes as3
is too large to affectdp[1]
ordp[2]
.
- When
In the end, dp[n]
gives us the count of the number of expressions that sum up to target
.
The method described balances the need to consider both including and excluding each number in nums
while ensuring each sum is only counted once. It utilizes memory efficiently by only maintaining a one-dimensional array rather than a full matrix that would be required in a naive implementation of dynamic programming for this problem.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the provided solution approach. Suppose we have nums = [1, 2, 3]
and target = 2
.
According to the solution approach, our first step is to calculate the sum s
of all numbers in nums
. Here, the sum is 1 + 2 + 3 = 6
.
Then we check if the total sum s
is less than target
or if s - target
is odd. In this case, 6
is not less than 2
, and 6 - 2
is even, so we proceed.
Our next step is to determine the size of the dp
array, which will help us count the number of ways to make up different sums. We calculate n = (s - target) / 2
, which is (6 - 2) / 2 = 2
.
Now we initialize our dp
array with zeros and set dp[0]
to 1
. So initially, our dp
array is [1, 0, 0]
.
Next, we iterate over each number v
in nums
. For each v
, we update the dp
array from n
down to v
:
-
For
v = 1
, updatedp[j]
fromj = 2
to1
. Thedp
array changes as follows:dp[1]
gets updated todp[1] + dp[1 - 1]
which isdp[1] = 0 + 1 = 1
.- The
dp
array is now[1, 1, 0]
.
-
For
v = 2
, updatedp[j]
fromj = 2
to2
:dp[2]
gets updated todp[2] + dp[2 - 2]
which isdp[2] = 0 + 1 = 1
.- The
dp
array is now[1, 1, 1]
.
-
For
v = 3
, since ourdp
array size is only3
, we don't need to update it forv = 3
because3
is larger thann
.
Finally, our dp
array is [1, 1, 1]
, and the dp[-1]
or dp[2]
indicates that there is 1
possible expression that can be created using nums
to sum up to target
, which is "1 + 2 - 3".
This walkthrough demonstrates how the dynamic programming approach effectively counts the number of expressions equating to the target without redundantly computing combinations.
Solution Implementation
1from typing import List
2
3class Solution:
4 def findTargetSumWays(self, nums: List[int], target: int) -> int:
5 # Calculate the sum of all numbers in the array
6 total_sum = sum(nums)
7
8 # Check if the target is achievable or not
9 # If the sum of nums is less than target, or the difference between sum and target
10 # is not an even number, then return 0 because target can't be achieved
11 if total_sum < target or (total_sum - target) % 2 != 0:
12 return 0
13
14 # Compute the subset sum we need to find to partition the array
15 # into two subsets that give the desired target on applying + and - operations
16 subset_sum = (total_sum - target) // 2
17
18 # Initialize a list for dynamic programming, with a size of subset_sum + 1
19 dp = [0] * (subset_sum + 1)
20
21 # There is always 1 way to achieve a sum of 0, which is by selecting no elements
22 dp[0] = 1
23
24 # Update the dynamic programming table
25 # For each number in nums, update the count of ways to achieve each sum <= subset_sum
26 for num in nums:
27 for j in range(subset_sum, num - 1, -1):
28 # Add the number of ways to achieve a sum of j before num was considered
29 dp[j] += dp[j - num]
30
31 # Return the number of ways to achieve subset_sum, which indirectly gives us the number of ways
32 # to achieve the target sum using '+' and '-' operations
33 return dp[-1]
34
35# Example usage:
36# solution = Solution()
37# result = solution.findTargetSumWays([1, 1, 1, 1, 1], 3)
38# print(result) # Outputs: 5
39
1class Solution {
2 public int findTargetSumWays(int[] nums, int target) {
3 // Initialize the sum of all numbers in nums
4 int sum = 0;
5 for (int num : nums) {
6 sum += num;
7 }
8
9 // If the sum is less than the target or (sum - target) is odd, it's not possible to partition
10 if (sum < target || (sum - target) % 2 != 0) {
11 return 0;
12 }
13
14 // Compute the subset sum needed for one side of the partition
15 int subsetSum = (sum - target) / 2;
16
17 // Initialize a DP array to store the number of ways to reach a particular sum
18 int[] dp = new int[subsetSum + 1];
19
20 // There's one way to reach the sum of 0 - by not including any numbers
21 dp[0] = 1;
22
23 // Go through every number in nums
24 for (int num : nums) {
25 // Update the DP table from the end to the start to avoid overcounting
26 for (int j = subsetSum; j >= num; j--) {
27 // Increase the current dp value by the value from dp[j - num]
28 dp[j] += dp[j - num];
29 }
30 }
31
32 // Return the number of ways to reach the target sum
33 return dp[subsetSum];
34 }
35}
36
1#include <vector>
2#include <numeric> // For using accumulate function
3
4class Solution {
5public:
6 int findTargetSumWays(vector<int>& nums, int target) {
7 // Calculate the sum of all numbers in the vector
8 int sum = std::accumulate(nums.begin(), nums.end(), 0);
9
10 // If the sum is less than the target or the adjusted sum is odd, return 0
11 if (sum < target || (sum - target) % 2 != 0) return 0;
12
13 // Calculate the new target (n) which is the sum to be found
14 int newTarget = (sum - target) / 2;
15
16 // Initialize the dynamic programming array with zeros
17 // and set dp[0] to 1 since there's one way to get sum 0: using no numbers
18 vector<int> dp(newTarget + 1, 0);
19 dp[0] = 1;
20
21 // Iterate over every number in the input array
22 for (int num : nums) {
23 // For each number, iterate backwards from the new target to the number's value
24 // This is to ensure we do not count any subset more than once
25 for (int j = newTarget; j >= num; --j) {
26 // Update the dp array to count additional ways to reach current sum (j)
27 // by adding the number of ways to reach the sum without the current number (j - num)
28 dp[j] += dp[j - num];
29 }
30 }
31
32 // Return the total number of ways to reach the 'newTarget', which corresponds
33 // to the number of ways to reach the original 'target' considering +/- signs
34 return dp[newTarget];
35 }
36};
37
1/**
2 * Calculates the number of ways to assign '+' and '-'
3 * to make the sum of nums be equal to target.
4 *
5 * @param {number[]} nums - Array of numbers to be used.
6 * @param {number} target - The target sum to be achieved.
7 * @return {number} - Number of ways to achieve the target sum.
8 */
9const findTargetSumWays = (nums: number[], target: number): number => {
10 // Calculate the sum of the input array elements
11 let sum: number = nums.reduce((acc, val) => acc + val, 0);
12
13 // If the sum is less than the target, or the difference is odd, there is no solution
14 if (sum < target || (sum - target) % 2 !== 0) {
15 return 0;
16 }
17
18 const totalNums: number = nums.length;
19 // Calculate the subset sum that we need to find
20 const subsetSum: number = (sum - target) / 2;
21 // Initialize a DP array for storing number of ways to sum up to j with array elements
22 let waysToSum: number[] = new Array(subsetSum + 1).fill(0);
23 waysToSum[0] = 1; // Base case - there's one way to have a sum of zero (using no elements)
24
25 // Fill the DP array
26 for (let i = 1; i <= totalNums; ++i) {
27 for (let j = subsetSum; j >= nums[i - 1]; --j) {
28 waysToSum[j] += waysToSum[j - nums[i - 1]]; // Update the ways to sum to j
29 }
30 }
31
32 // Return the total ways to achieve the subset sum, which is equivalent to the target
33 return waysToSum[subsetSum];
34};
35
36export { findTargetSumWays }; // Exporting the function to be used in other modules
37
Time and Space Complexity
The time complexity of the algorithm is O(len(nums) * n)
, where len(nums)
is the number of elements in the input list nums
, and n
is the computed value (sum(nums) - target) // 2
. This is because the algorithm consists of a nested loop, where the outer loop runs for each element in nums
, and the inner loop runs from n
down to the value of the current element v
.
The space complexity of the algorithm is O(n + 1)
, which simplifies to O(n)
, as there is a one-dimensional list dp
of size n + 1
elements used to store the intermediate results for the subsets that sum up to each possible value from 0
to n
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following problems can be solved with backtracking (select multiple)
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.