Explain how to find a target sum in an array.

Medium

Unlock detailed company stats for this questionUpgrade

Determine the Number of Ways to Assign Symbols to Reach a Target Sum. You are given a list of non-negative integers, a1, a2, ..., an, and a target sum S. Your task is to assign each integer in the list a symbol + or - and calculate how many different ways there are to arrange these symbols such that the sum of the integers equals S after applying the assigned symbols.

For example, if you have the list [1, 1, 1, 1, 1] and the target sum 3, one way to reach the target sum is to assign + to three 1s and - to two 1s, like so: +1 +1 +1 +1 -1. Another way could be +1 -1 +1 +1 +1. You need to return the total number of unique arrangements that meet the target sum S.

Examples


nums = [1, 1, 1, 1, 1]
targetSum = 3
output: 5

nums = [1, 2, 1]
targetSum = 2
output: 2

nums = [1, 2, 7, 1, 5, 3]
targetSum = 8
output: -1 (Explanation: Since the total sum of the numbers plus the target is odd, it's not possible to reach the target sum.)

The original problem asks for the number of ways to assign symbols (+ or -) to a list of numbers such that their sum equals a target sum S. This problem can be converted into a problem of finding subsets of the given numbers whose sum equals (totalSum + S) / 2. This is because if we can find subsets whose sum equals (totalSum + S) / 2, the remaining numbers will naturally form the other subset that sums to (totalSum - S) / 2, which effectively gives us the desired configuration of symbols.

Why (totalSum + S) / 2?

Given a list of numbers $\text{nums} = [a_1, a_2, ..., a_n]$ , we need to assign either a $+$ or a $-$ to each number so that the total sum equals a target $S$ .

Let's denote the sum of the entire list as $\text{sum(nums)} = \text{totalSum}$ .

The problem can be rephrased as finding subsets of $\text{nums}$ such that the difference between the sum of elements in the subset and the sum of elements not in the subset equals $S$ .

Formulating the Equation:

Let $P$ be the sum of elements with a $+$ sign and $N$ be the sum of elements with a $-$ sign.
We need $P - N = S$ .
We also know that $P + N = \text{totalSum}$ , where $\text{totalSum}$ is the sum of all elements in $\text{nums}$ .

Combining the Equations: Adding these two equations:

P - N + P + N = S + \text{totalSum}\\ 2P = S + \text{totalSum}

Therefore, $P = \frac{S + \text{totalSum}}{2}$ .

The problem now reduces to finding subsets of $\text{nums}$ whose sum equals $\frac{S + \text{totalSum}}{2}$ .

Approach

We define a recursive function find_subset that takes an index, the list of numbers, the target subset sum, and a memoization table (dp). The function recursively explores two possibilities at each step:

Include the current number in the subset.
Exclude the current number from the subset.

The base cases for the recursion are:

If the target subset sum (s) is zero, it means we found a valid subset, so we return 1.
If we reach the end of the list without finding the subset sum, we return 0.
If we have already computed the value for the current state (index and subset sum), we return the stored value from the memoization table to avoid redundant calculations.

The changeSigns function calculates the total sum of the numbers and checks if it is possible to partition them to meet the required target sum S. If it is possible, it initializes the memoization table and calls the find_subset function to compute the number of ways to achieve the target sum.

Solution

Time Complexity: The time complexity of this solution is O(n x (totalSum + S)) / 2, where n is the number of elements in the input list. This is because each state in the memoization table can be computed in constant time, and there are n x (totalSum + S) / 2 states to fill.

Space Complexity: The space complexity of this solution is O(n x (totalSum + S) / 2) due to the memoization table used to store intermediate results. Additionally, the recursive call stack can go up to O(n) in the worst case, but this is dominated by the space required for the memoization table.

Related courses

Course

Software Engineering Interview Prep

Land your dream software engineering role at Google, Amazon, Microsoft, Meta, Apple, and other top companies. Learn from mock interviews, frameworks, and advice from senior candidates—practice data structures, algorithms, system design, people management, behavioral interviews, and more.

Course

System Design Interviews

Learn how to answer the latest system design questions across product, infrastructure, and AI domains. Features in-depth video examples, written breakdowns, and helpful reference patterns. Watch senior engineers and managers answer these questions in mock interview videos.

Explain how to find a target sum in an array.

Roles

Companies

Categories