Target Sum
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 , we need to assign either a or a to each number so that the total sum equals a target .
Let's denote the sum of the entire list as .
The problem can be rephrased as finding subsets of such that the difference between the sum of elements in the subset and the sum of elements not in the subset equals .
Formulating the Equation:
- Let be the sum of elements with a sign and be the sum of elements with a sign.
- We need .
- We also know that , where is the sum of all elements in .
Combining the Equations: Adding these two equations:
Therefore, .
The problem now reduces to finding subsets of whose sum equals .
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
def find_subset(index, nums, s, dp):
if s == 0:
return 1
if index == len(nums):
return 0
if dp[s][index] != -1:
return dp[s][index]
# including current elem
sum1 = find_subset(index+1, nums, s - nums[index], dp)
sum2 = find_subset(index+1, nums, s, dp)
dp[s][index] = sum1 + sum2
return sum1 + sum2
def changeSigns(nums, S):
totalSum = S + sum(nums)
if totalSum % 2 != 0:
return -1
total = totalSum // 2
dp = [[-1 for _ in range(len(nums))] for _ in range(total + 1)]
return find_subset(0, nums, total, dp)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.
Watch our mock Flipkart SWE (software engineering) interview. Neamah asks Rohan (Flipkart SWE) the Target Sum leetcode question.
// C++ program to print the count of // subsets with sum equal to the given value X
#include <iostream> using namespace std;
// Recursive function to return the count // of subsets with sum equal to the given value int subsetSum(int arr[], int n, int i, int sum, int count) { // The recursion is stopped at N-th level // where all the subsets of the given array // have been checked if (i == n) {
// Incrementing the count if sum is // equal to 0 and returning the count if (sum == 0) { count++; } return count; } // Recursively calling the function for two cases // Either the element can be counted in the subset // If the element is counted, then the remaining sum // to be checked is sum - the selected element // If the element is not included, then the remaining sum // to be checked is the total sum count = subsetSum(arr, n, i + 1, sum - arr[i], count); count = subsetSum(arr, n, i + 1, sum, count); return count;}
// Driver code int main() { int arr[] = { 1, 2, 3, 4, 5 }; int sum = 10; int n = sizeof(arr) / sizeof(arr[0]);
cout << subsetSum(arr, n, 0, sum, 0);}