Problem Statement
Given an array nums of n integers and an integer target, build an expression using the integers from nums where each integer can be prefixed with either a '+' or '-' sign. The goal is to achieve the target sum by evaluating all possible combinations of these signs. Determine the number of ways to achieve the target sum and return your answer with modulo 109+7.
Examples
Example 1:
Input: nums = [1, 2, 3, 4, 5], target = 5
Output: 3
Explanation:
There are 3 ways to assign signs to achieve the target sum of 5:
+1 -2 +3 +4 -5 = 5
+1 +2 -3 +4 +1 = 5
-1 +2 +3 +4 -3 = 5Example 2:
Input: nums = [1, 2, 1], target = 2
Output: 2
Explanation:
There are 2 ways to assign signs to achieve the target sum of 2:
1. +1 +2 -1 = 2
2. -1 +2 +1 = 2Example 3:
Input: nums = [100], target = -200
Output: 0
Explanation:
It is not possible to achieve the target sum of -200 using the given nums. Therefore, the output is 0.Different Approaches
1️⃣ Recursive Approach
The first approach that comes to our mind is to generate all subsequences and try both options of placing ‘-’ and ‘+’ signs and count the expression if it evaluates the answer. This surely will give us the answer but we can try something familiar to the concept we studied in the article Count Partitions with Given Difference.
Understanding:
We can say that the given ‘target’ can be expressed as addition of two integers (say S1 and S2).
S1 + S2 = target – (i)Now, if the given array is [a,b,c,d,e], we want to place ‘+’ or ‘-’ signs in front of every array element and then add it. One example is :
+a-b-c+d+e which can be written as (+a+d+e) + (-b-c).Therefore, we can say that:
S1=(+a+d+e) and S2=(-b-c) for this example.If we calculate the total sum of elements of the array (say totSum), we can can say that,
S1 = totSum - S2 – (ii)Now solving for equations (i) and (ii), we can say that:
S2 = (totSum - target)/2 – (iii)Therefore this question is modified to “Count Number of subsets with sum (totSum - target)/2 ”. This is exactly what we had discussed in the article Count Subsets with Sum K.
There's some edge cases that need to be handled :
- As the array elements are positive integers including zero, we don’t want to find the case when S2 is negative or we can say that totSum is lesser than D, therefore if totSum.
From here on we will discuss the approach to “Count Subsets with Sum K” with the required modifications. Moreover, as the array elements can also contain 0, we will handle it as discussed above.
Steps to form the recursive solution:
- Express the problem in terms of indexes: The array will have an index but there is one more parameter “target”. We are given the initial problem to find whether there exists in the whole array a subsequence whose sum is equal to the target.
- So, initially, we need to find(n-1, target) which means that we are counting the number of subsequences in the array from index 0 to n-1, whose sum is equal to the target.
- Try out all possible choices at a given index: As, all the subsequences need to be generated. We will use the pick/non-pick technique, we have two choices:
- Exclude the current element from the subsequence: Try to find a subsequence without considering the current index element. For this, make a recursive call to f(ind-1,target).
- Include the current element in the subsequence: Try to find a subsequence by considering the current index as element as part of subsequence. As arr[ind] is included, the updated target will be target - arr[ind]. Therefore, call f(ind-1,target-arr[ind]).
Note: Consider the current element in the subsequence only when the current element is less than or equal to the target.
f(ind, target){
notTake = 0 + f(ind-1, target)
take = 0
if(arr[ind] <= target)
take = f(ind-1, target-arr[ind])
}- Return sum of taken and notTaken: As we have to return the total count of subsets with the target sum, return the sum of 'taken' and 'notTaken' from our recursive call.
f(ind, target){
notTake = 0 + f(ind-1, target)
take = 0
if(arr[ind] <= target)
take = f(ind-1, target-arr[ind])
return notTaken + taken
}- Base Cases:
- If target == 0, it means that we have already found the subsequence from the previous steps, so return 1.
- Also, if ind==0, it means we are at the first element, so return arr[ind]==target. If the element is equal to the target return 1 else return 0.
Code:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/**
* Helper function to calculate the number of ways to achieve the target sum
* using recursive calls.
* @param nums The array of integers.
* @param currentIndex The current index in the array.
* @param remainingTarget The remaining sum to achieve.
* @return The number of ways to achieve the target sum.
*/
int calculateWays(vector<int>& nums, int currentIndex, int remainingTarget) {
// Base case: If the target is achieved
if (remainingTarget == 0) {
return 1;
}
// Base case: If we've exhausted the array without achieving the target
if (currentIndex >= nums.size()) {
return 0;
}
// Recursive case: Include or exclude the current element
int includeCurrent = calculateWays(nums, currentIndex + 1, remainingTarget - nums[currentIndex]);
int excludeCurrent = calculateWays(nums, currentIndex + 1, remainingTarget);
// Return the total number of ways
return includeCurrent + excludeCurrent;
}
/**
* Function to calculate the number of ways to assign '+' or '-' signs
* to achieve the target sum.
* @param n The size of the nums array.
* @param target The target sum to achieve.
* @param nums The array of integers.
* @return The number of ways to achieve the target sum.
*/
int targetSum(int n, int target, vector<int>& nums) {
// Calculate the total sum of the array
int totalSum = 0;
for (int num : nums) {
totalSum += num;
}
// Edge case: If the target is not achievable due to parity or range
if ((totalSum - target) < 0 || (totalSum - target) % 2 != 0) {
return 0;
}
// Calculate the subset sum to find (equivalent to the problem transformation)
int subsetSum = (totalSum - target) / 2;
// Call the recursive helper function
return calculateWays(nums, 0, subsetSum);
}
};
Complexity Analysis:
- Time Complexity:
O(2^n)- As each index has 2 choices and there are total of
nelements.
- As each index has 2 choices and there are total of
- Space Complexity:
O(n)- As we are using recursive stack space of
O(n).
- As we are using recursive stack space of
2️⃣ Memoization
If we draw the recursion tree, we will see that there are overlapping subproblems. Hence the DP approaches can be applied to the recursive solution.
In order to convert a recursive solution to memoization the following steps will be taken:
- Declare a dp array of size [n][target+1]: As there are two changing parameters in the recursive solution, 'ind' and 'target'. The maximum value 'ind' can attain is (n), where n is the size of array and for 'target' only values between 0 to target. Therefore, we need 2D dp array.
- The dp array stores the calculations of subproblems. Initialize dp array with -1, to indicate that no subproblem has been solved yet.
- While encountering an overlapping subproblem: When we come across a subproblem, for which the dp array has value other than -1, it means we have found a subproblem which has been solved before hence it is an overlapping subproblem. No need to calculate it's value again just retrieve the value from dp array and return it.
- Store the value of subproblem: Whenever, a subproblem is encountered and it is not solved yet(the value at this index will be -1 in the dp array), store the calculated value of subproblem in the array.
Code:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
const int MOD = 1e9 + 7;
/**
* Helper function to calculate the number of ways to achieve the target sum
* using recursive calls.
* @param nums The array of integers.
* @param currentIndex The current index in the array.
* @param remainingTarget The remaining sum to achieve.
* @param dp The memoization table to avoid recalculating subproblems.
* @return The number of ways to achieve the target sum.
*/
int calculateWays(vector<int>& nums, int currentIndex, int remainingTarget, vector<vector<int>>& dp) {
// Base case: If the target is achieved
if (remainingTarget == 0) {
return 1;
}
// Base case: If we've exhausted the array or the target is negative
if (currentIndex >= nums.size() || remainingTarget < 0) {
return 0;
}
// Check if the result is already computed
if(dp[currentIndex][remainingTarget] != -1) {
return dp[currentIndex][remainingTarget];
}
// Recursive case: Include or exclude the current element
int includeCurrent = calculateWays(nums, currentIndex + 1, remainingTarget - nums[currentIndex], dp);
int excludeCurrent = calculateWays(nums, currentIndex + 1, remainingTarget, dp);
// Store and return the total number of ways
return dp[currentIndex][remainingTarget] = (includeCurrent + excludeCurrent) % MOD;
}
/**
* Function to calculate the number of ways to assign '+' or '-' signs
* to achieve the target sum.
* @param n The size of the nums array.
* @param target The target sum to achieve.
* @param nums The array of integers.
* @return The number of ways to achieve the target sum.
*/
int targetSum(int n, int target, vector<int>& nums) {
// Calculate the total sum of the array
int totalSum = 0;
for (int num : nums) {
totalSum += num;
}
// Edge case: If the target is not achievable due to parity or range
if ((totalSum - target) < 0 || (totalSum - target) % 2 != 0) {
return 0;
}
// Calculate the subset sum to find (equivalent to the problem transformation)
int subsetSum = (totalSum - target) / 2;
// If subsetSum is negative, return 0 as it's impossible to achieve it
if (subsetSum < 0) {
return 0;
}
// Initialize the dp table for memoization
vector<vector<int>> dp(nums.size(), vector<int>(subsetSum + 1, -1));
// Call the recursive helper function
return calculateWays(nums, 0, subsetSum, dp);
}
};
Complexity Analysis:
- Time Complexity:
O(N*target), There are 'N*target' states therefore at max ‘N*target’ new problems will be solved. - Space Complexity:
O(N*target) + O(N), As we are using a recursion stack space(O(N)) and a 2D array ( O(N*target)).