Similar Problems
Similar Problems not available
Target Sum  Leetcode Solution
LeetCode: Target Sum Leetcode Solution
Difficulty: Medium
Topics: backtracking array dynamicprogramming
Target Sum problem on LeetCode is a problem of finding out the number of possible combinations of target sum using given array of numbers. The detailed solution to Target Sum problem is given below:
Problem Statement: You are given a list of nonnegative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and . For each integer, you should choose one from + and  as its new symbol.
Find out how many ways to assign symbols to make sum of integers equal to target S.
Solution: The solution to this problem is based on dynamic programming approach where we maintain a 2D matrix to keep track of all possible sums for each index and each target value.
Steps:

Initialize a 2D matrix dp of size (n+1)(2sum+1) with all values as 0. (where n is the length of array and sum is the total sum of array elements) Here, dp[i][j] will represent the number of ways to achieve a sum of j using first i elements of the array.

Set dp[0][sum] to 1, since it will represent zero elements used to get the sum.

For each element in the array, we iterate over all possible values of j and update dp[i][j].
a. dp[i][j+nums[i1]] += dp[i1][j]
This means if we add nums[i1] to include current element in the sum, then the required target becomes j+nums[i1] and we can add all possible ways we could have achieved a target of j without including current element by adding the number of combinations from previous i1 elements to the dp[i][j+nums[i1]].
b. dp[i][jnums[i1]] += dp[i1][j]
This means if we subtract nums[i1] to include current element in the sum, then the required target becomes jnums[i1] and we can add all possible ways we could have achieved a target of j without including current element by adding the number of combinations from previous i1 elements to the dp[i][jnums[i1]].

Return dp[n][sum+S] which will represent the number of ways to achieve the target sum S using all elements of the array.
Code:
class Solution { public: int findTargetSumWays(vector<int>& nums, int S) { int n = nums.size(); int sum = accumulate(nums.begin(), nums.end(), 0); if (sum < S  (sum + S) % 2 != 0) return 0; // if sum is less than S or sum+S is odd, return 0 int target = (sum + S) / 2; // target value which we need to achieve vector<vector<int>> dp(n+1, vector<int>(2sum+1, 0)); dp[0][sum] = 1; for (int i = 1; i <= n; i++) { for (int j = 0; j < 2sum+1; j++) { if (j+nums[i1] < 2*sum+1) dp[i][j] += dp[i1][j+nums[i1]]; if (jnums[i1] >= 0) dp[i][j] += dp[i1][jnums[i1]]; } } return dp[n][target]; } };
Time Complexity: O(nsum) where n is the length of array and sum is the total sum of array elements Space Complexity: O(nsum)
This algorithm can also be optimized to use space in O(sum) as it is only dependent on value of sum.
Target Sum Solution Code
1