Jobs

Interviews

Discussions

Target Sum

Medium

2 views

Topics:

ArraysDynamic ProgrammingRecursion

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

Target Sum

Medium

2 views

Topics:

ArraysDynamic ProgrammingRecursion

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

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the numbers in the input array be negative, positive, or zero?
How large can the input array be, and what is the possible range of values for the numbers within the array and the target sum?
If there are multiple combinations of numbers that sum up to the target, should I return just one or all of them? If only one, is there any preference as to which one to return?
Are duplicate numbers allowed in the input array, and if so, should I treat them as distinct numbers when finding combinations?
If no combination of numbers sums up to the target, what should I return (e.g., null, empty array, or a specific error code)?

Brute Force Solution

Approach

The brute force approach to finding a target sum involves exploring every single possible combination of pluses and minuses before each number. We then evaluate the expression to see if it matches the target. This is like trying every possible path to see which one leads to the destination.

Here's how the algorithm would work step-by-step:

Consider the first number. It can either be positive or negative.
For each of those options, consider the second number. Again, it can be positive or negative.
Continue this pattern for all the numbers in the input. Each number doubles the number of possibilities we need to check.
Once we've assigned a plus or minus to every number, we compute the resulting sum.
If the sum equals the target, we count that as one possible solution.
Repeat this process, trying every single combination of pluses and minuses until we have explored them all.
Finally, report the total count of combinations that resulted in the target sum.

Code Implementation

def target_sum_brute_force(numbers, target): 
    number_of_ways = 0

    def calculate_target_sum(index, current_sum):
        nonlocal number_of_ways

        # If we've processed all numbers, check if the sum matches the target
        if index == len(numbers):
            if current_sum == target:
                number_of_ways += 1
            return

        # Explore adding the current number
        calculate_target_sum(index + 1, current_sum + numbers[index])

        # Explore subtracting the current number
        # We explore two possibilities: add or subtract
        calculate_target_sum(index + 1, current_sum - numbers[index])

    # Initiate the recursive calls starting from the first number
    # Initiate recursion with index 0 and a current sum of 0.
    calculate_target_sum(0, 0)

    return number_of_ways

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach explores every possible combination of plus and minus signs for each of the n numbers in the input array. Each number has two choices (+ or -), so the total number of combinations is 2 * 2 * ... * 2 (n times), which equals 2^n. For each of these 2^n combinations, we calculate the sum of the resulting expression, which takes O(n) time. However, the dominant factor is the exponential growth of the combinations. Therefore, the overall time complexity is O(2^n).

Space Complexity

O(N) – The brute force approach uses recursion. In the worst case, the recursive calls will continue until each of the N numbers in the input array has been assigned a plus or a minus sign. This leads to a recursion depth of N. Each recursive call requires a stack frame to store local variables and the return address, resulting in auxiliary space proportional to the depth of the recursion. Therefore, the space complexity is O(N).

Optimal Solution

Approach

The core idea is to think about the problem as exploring all possible combinations of adding or subtracting each number. However, instead of explicitly building out every combination, we can use a clever trick to count the combinations efficiently. This approach avoids redundant calculations and provides a faster solution.

Here's how the algorithm would work step-by-step:

Imagine that numbers with plus signs and numbers with minus signs make up two distinct groups.
Notice that the total sum of all the numbers is fixed.
Recognize that if you know the sum of just one of those groups (either the plus group or the minus group), you can easily figure out the sum of the other group.
Realize that finding the number of ways to achieve the target sum is the same as finding the number of ways to form one of these groups (for example, the plus group) with a specific sum.
Reframe the problem as: 'How many ways can you pick numbers from the list such that they add up to a certain value (the sum of the plus group)?'
Now, instead of directly trying out plus or minus for each number, focus on finding subsets that add up to the target sum (the plus group sum). You can use efficient techniques to count the number of such subsets.
This re-framing and focusing on subset sums lets you avoid explicitly generating all the plus/minus combinations, making the computation significantly faster.

Code Implementation

def target_sum(numbers, target):    total_sum = sum(numbers)
    # The target sum is unreachable if it's out of bounds.
    if (total_sum + target) % 2 != 0 or abs(target) > total_sum:
        return 0
    sum_of_positive_numbers = (total_sum + target) // 2
    # This table stores number of subsets summing to specific values.
    subset_sums = [0] * (sum_of_positive_numbers + 1)
    subset_sums[0] = 1
    for number in numbers:
        # Iterate backwards to avoid overwriting values.
        for current_sum in range(sum_of_positive_numbers, number - 1, -1):

            # Accumulate counts of subsets summing to current_sum.
            subset_sums[current_sum] += subset_sums[current_sum - number]

    return subset_sums[sum_of_positive_numbers]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n*s) – The algorithm reframes the target sum problem into a subset sum problem. We iterate through each number in the input array (n elements). For each number, we update the count of subsets summing to different possible totals from 0 to s (the target sum for the positive subset, derived from the original target and the total sum of the input array). The size of the subset sum table depends on the number of elements and the sum of the subset. Therefore, the time complexity depends on both the number of elements, n, and the target sum, s, giving us a runtime of O(n*s).

Space Complexity

O(N * targetSum) – The re-framing of the problem as a subset sum problem typically involves dynamic programming to efficiently count the number of subsets. This approach uses a 2D array (or similar structure) of size N * targetSum (or potentially a smaller range depending on optimization), where N is the number of elements in the input array, and targetSum is the sum needed to be achieved by the plus group. Therefore, the auxiliary space needed scales linearly with both the input array size and the target sum.

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty list or null to indicate no solution is possible.
Array with a single element	Return an empty list or null since a pair requires at least two elements.
All numbers in the array are the same, and the target is twice that number	Check if the same index is used twice by verifying the count or explicit index check.
Array contains large positive and negative numbers resulting in potential integer overflow	Use a data type with a larger range, or check for potential overflow before performing the addition.
No solution exists, the target sum is unachievable	Return an empty list or null to indicate that no valid pair exists.
The array contains duplicate pairs that sum to the target	Return only distinct pairs or handle duplicates appropriately based on the problem definition.
The target sum is zero and the array contains positive and negative numbers that can cancel out	The hashmap should accurately identify complimenting pairs.
Large input array size impacting time and space complexity	The solution needs to be optimized, potentially using hashmaps or sorting with early termination checks, ensuring O(n) or O(n log n) time complexity.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the numbers in the input array be negative, positive, or zero?
How large can the input array be, and what is the possible range of values for the numbers within the array and the target sum?
If there are multiple combinations of numbers that sum up to the target, should I return just one or all of them? If only one, is there any preference as to which one to return?
Are duplicate numbers allowed in the input array, and if so, should I treat them as distinct numbers when finding combinations?
If no combination of numbers sums up to the target, what should I return (e.g., null, empty array, or a specific error code)?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Consider the first number. It can either be positive or negative.
For each of those options, consider the second number. Again, it can be positive or negative.
Continue this pattern for all the numbers in the input. Each number doubles the number of possibilities we need to check.
Once we've assigned a plus or minus to every number, we compute the resulting sum.
If the sum equals the target, we count that as one possible solution.
Repeat this process, trying every single combination of pluses and minuses until we have explored them all.
Finally, report the total count of combinations that resulted in the target sum.

Code Implementation

def target_sum_brute_force(numbers, target): 
    number_of_ways = 0

    def calculate_target_sum(index, current_sum):
        nonlocal number_of_ways

        # If we've processed all numbers, check if the sum matches the target
        if index == len(numbers):
            if current_sum == target:
                number_of_ways += 1
            return

        # Explore adding the current number
        calculate_target_sum(index + 1, current_sum + numbers[index])

        # Explore subtracting the current number
        # We explore two possibilities: add or subtract
        calculate_target_sum(index + 1, current_sum - numbers[index])

    # Initiate the recursive calls starting from the first number
    # Initiate recursion with index 0 and a current sum of 0.
    calculate_target_sum(0, 0)

    return number_of_ways

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine that numbers with plus signs and numbers with minus signs make up two distinct groups.
Notice that the total sum of all the numbers is fixed.
Recognize that if you know the sum of just one of those groups (either the plus group or the minus group), you can easily figure out the sum of the other group.
Realize that finding the number of ways to achieve the target sum is the same as finding the number of ways to form one of these groups (for example, the plus group) with a specific sum.
Reframe the problem as: 'How many ways can you pick numbers from the list such that they add up to a certain value (the sum of the plus group)?'
Now, instead of directly trying out plus or minus for each number, focus on finding subsets that add up to the target sum (the plus group sum). You can use efficient techniques to count the number of such subsets.
This re-framing and focusing on subset sums lets you avoid explicitly generating all the plus/minus combinations, making the computation significantly faster.

Code Implementation

def target_sum(numbers, target):    total_sum = sum(numbers)
    # The target sum is unreachable if it's out of bounds.
    if (total_sum + target) % 2 != 0 or abs(target) > total_sum:
        return 0
    sum_of_positive_numbers = (total_sum + target) // 2
    # This table stores number of subsets summing to specific values.
    subset_sums = [0] * (sum_of_positive_numbers + 1)
    subset_sums[0] = 1
    for number in numbers:
        # Iterate backwards to avoid overwriting values.
        for current_sum in range(sum_of_positive_numbers, number - 1, -1):

            # Accumulate counts of subsets summing to current_sum.
            subset_sums[current_sum] += subset_sums[current_sum - number]

    return subset_sums[sum_of_positive_numbers]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty list or null to indicate no solution is possible.
Array with a single element	Return an empty list or null since a pair requires at least two elements.
All numbers in the array are the same, and the target is twice that number	Check if the same index is used twice by verifying the count or explicit index check.
Array contains large positive and negative numbers resulting in potential integer overflow	Use a data type with a larger range, or check for potential overflow before performing the addition.
No solution exists, the target sum is unachievable	Return an empty list or null to indicate that no valid pair exists.
The array contains duplicate pairs that sum to the target	Return only distinct pairs or handle duplicates appropriately based on the problem definition.
The target sum is zero and the array contains positive and negative numbers that can cancel out	The hashmap should accurately identify complimenting pairs.
Large input array size impacting time and space complexity	The solution needs to be optimized, potentially using hashmaps or sorting with early termination checks, ensuring O(n) or O(n log n) time complexity.