We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Target Sum

Number: 494

Difficulty: Medium

Paid? No

Companies: Meta, Amazon, Microsoft, Google, Bloomberg, Pinterest, Myntra, Salesforce, Apple

Problem Description

Given an array of integers, nums, and a target integer, assign a '+' or '-' sign to each number in nums so that when concatenated, the arithmetic expression evaluates to the target. Return the number of different expressions that can be built to achieve the target.

Key Insights

  • The problem can be converted into a subset sum problem by considering two groups: numbers with a '+' sign and numbers with a '-' sign.
  • Let the sum of numbers with a '+' sign be sum(P) and with a '-' sign be sum(N). Then the problem reduces to solving:
    • sum(P) - sum(N) = target
    • and sum(P) + sum(N) = totalSum, where totalSum is the sum of all numbers in nums.
  • From these equations, we derive sum(P) = (target + totalSum) / 2.
  • We only proceed if (target + totalSum) is even and not negative; otherwise, there are no valid expressions.
  • Dynamic programming is used to count the number of subsets that sum to sum(P).

Space and Time Complexity

Time Complexity: O(n * subsetSum), where n is the length of the nums array and subsetSum = (target + totalSum)/2. Space Complexity: O(subsetSum), as we use a one-dimensional DP array.

Solution

The solution converts the problem into a subset sum DP problem. First, compute the total sum of the array. If (target + totalSum) is not even or target is greater than totalSum, return 0 since no valid configuration exists. Otherwise, compute the required subset sum (subsetSum) as (target + totalSum) / 2 and use a dynamic programming array to count the number of ways to reach subsetSum. The DP approach iterates through each number in the array, updating the counts using a reverse iteration to ensure each number is only used once.

Code Solutions

# Define a function to compute the number of ways to reach the target sum.
def findTargetSumWays(nums, target):
    # Calculate the total sum of all numbers in the list.
    total_sum = sum(nums)
    # If the target is greater than total_sum, or (target + total_sum) is odd, no solution exists.
    if target > total_sum or (target + total_sum) % 2 == 1:
        return 0

    # Compute the required subset sum.
    subset_sum = (target + total_sum) // 2
    # Initialize the dp array with zeros, with dp[0] set to 1.
    dp = [0] * (subset_sum + 1)
    dp[0] = 1

    # Update the dp array for each number in nums.
    for num in nums:
        # Iterate backwards to ensure each number is only counted once.
        for s in range(subset_sum, num - 1, -1):
            dp[s] += dp[s - num]
    return dp[subset_sum]

# Example usage:
print(findTargetSumWays([1,1,1,1,1], 3))  # Expected output: 5
← Back to All Questions