494. Target Sum
Target Sum (LeetCode 494) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Dynamic Programming (DP) Patterns pattern, in the 1D Array (0/1 Knapsack Subset Sum Style) subpattern.
- NeetCode 150 · #115 of 150 · 2-D Dynamic Programming
- NeetCode 250 · #198 of 250 · 2-D Dynamic Programming
How to solve Target Sum
Target Sum is a 0/1 Knapsack and Subset Sum problem, part of Dynamic Programming (DP) Patterns. Solve 0/1 knapsack, partition equal subset sum, and target sum problems.
Work towards the solution in these steps:
- Consider how dynamic programming can help count the number of ways to reach a target by making decisions at each element.
- Think about representing the problem as choosing subsets with positive and negative signs to achieve the target sum.
- Try to transform the problem into a subset sum variant where you find the number of subsets that satisfy a particular sum condition.
The reference solution runs in O(n * S) time and O(S) space.
The Target Sum solution and editorial walks through the full approach with reference code.
Problem statement
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 <= 20
- 0 <= nums[i] <= 1000
- 0 <= sum(nums[i]) <= 1000
- -1000 <= target <= 1000
Topics and companies
Topics: Array, Dynamic Programming, Backtracking.
Reported in interviews at Adobe, Amazon, Bloomberg, Facebook, Google, Microsoft.
How to practise Target Sum on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n * S) time and O(S) space.
Open Target Sum in the code editor, or read the Target Sum editorial for a worked solution with its approach and complexity analysis.
Where Target Sum sits in the DSA pattern sheet
- Dynamic Programming (DP) Patterns pattern guide
- 1D Array (0/1 Knapsack Subset Sum Style) subpattern
- The full DSA patterns sheet
Problems related to Target Sum
Other problems that use the same 1D Array (0/1 Knapsack Subset Sum Style) and Dynamic Programming (DP) Patterns techniques:
- Last Stone Weight II — Medium, same subpattern
- Partition Equal Subset Sum — Medium, same subpattern
- Best Time to Buy and Sell Stock — Easy, same pattern
- Best Time to Buy and Sell Stock II — Medium, same pattern
- Best Time to Buy and Sell Stock III — Hard, same pattern
- Best Time to Buy and Sell Stock IV — Hard, same pattern
Target Sum FAQ
What is the LeetCode number of Target Sum?
Target Sum is LeetCode problem 494, rated Medium.
What pattern is used to solve Target Sum?
Target Sum is a 0/1 Knapsack and Subset Sum problem. It belongs to the Dynamic Programming (DP) Patterns pattern, in the 1D Array (0/1 Knapsack Subset Sum Style) subpattern.
What is the time complexity of Target Sum?
The reference solution runs in O(n * S) time and O(S) space.
Which companies ask Target Sum?
Target Sum has been reported in interviews at Adobe, Amazon, Bloomberg, Facebook, Google, Microsoft.