Approach 1: Recursion
It is easy to identify that the problem can be solved using recursion as for each number we have two options: assign + sign or - sign. The problem with this approach is that is pretty time taking as the time complexity will be O(2^n) [two choices for each number].
int findTargetSumWays(vector<int>& nums, int S) {
unordered_map<string,int> memo;
return helper(nums, S, 0, 0);
}
int helper (vector<int>& nums, int& target, int currSum, int idx) {
if (idx == nums.size()) {
if (currSum == target)
return 1;
return 0;
}
string key = to_string(currSum)+","+to_string(idx);
int plus = helper(nums, target, currSum+nums[idx], idx+1);
int minus = helper(nums, target, currSum-nums[idx], idx+1);
return plus + minus;
}
If you make a recursion tree, it is easy to identify that the subproblems are overlapping (see below). Hence, we should employ memoization.
Input = [1,1,1], S = 1
[x,y] represents x as the current sum and y as the index
[0,0]
/ \
[1,1] [-1,1]
/ \ / \
[2,2] [0,2] [0,2] [-2,2]
/ | / \ | \ \ \
[3,3] | [1,3] | [1,3]\ [-1,3]\
[1,3] [-1,3] [-1,3] [-1,3]
Recursion + Memoization:
If you see the above recursion code, you’ll notice that we have to memoize the number of ways for each current sum and index pair. I did it using a map with “
int findTargetSumWays(vector<int>& nums, int S) {
unordered_map<string,int> memo;
return helper(nums, S, 0, 0, memo);
}
int helper (vector<int>& nums, int& target, int currSum, int idx, unordered_map<string,int>& memo) {
if (idx == nums.size()) {
if (currSum == target)
return 1;
return 0;
}
string key = to_string(currSum)+","+to_string(idx);
if (memo.find(key) != memo.end())
return memo[key];
int plus = helper(nums, target, currSum+nums[idx], idx+1, memo);
int minus = helper(nums, target, currSum-nums[idx], idx+1, memo);
memo[key] = plus+minus;
return plus + minus;
}
Approach 2: Dynamic Programming
The problem can be reduced to a classical 0/1 Knapsack Problem where instead of deciding whether to pick an element or not we have to decide whether to assign it a + sign or a - sign. See solution below having explanation:
int findTargetSumWays(vector<int>& nums, int S) {
// knapsack problem
// define dp[i][j] as no. of ways of making sum = j using first i elements
// the sum can be from -total_sum to +total_sum
// dp[i][j] = dp[i-1][j+nums[i-1]] + dp[i-1][j-nums[i-1]]
// ^ ^
// assuming the i-th no. to be -ve i-th no. positive
int total_sum = 0;
for (int i : nums) total_sum += i;
if (S < -total_sum || S > total_sum) return 0;
int r = nums.size()+1, c = 2*total_sum+1;
vector<vector<int>> dp(r, vector<int>(c, 0));
dp[0][total_sum] = 1;
/*
Input: nums = [1, 1, 1], S = 1
DP array:
Sum -> -3 -2 -1 0 1 2 3
Idx 0 1 2 3 4 5 6
0 0 0 0 1 0 0 0
1 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0
3 0 0 0 0 0* 0 0
dp[3][4] to be returned (star marked)
*/
for (int i=1; i<r; i++) {
for (int j=0; j<c; j++) {
if (j-nums[i-1]>=0) dp[i][j] += dp[i-1][j-nums[i-1]];
if (j+nums[i-1]<c) dp[i][j] += dp[i-1][j+nums[i-1]];
}
}
return dp[r-1][total_sum+S];
}