Target Sum - Leetcode Solution

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 non-negative 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:

1. 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.

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

3. For each element in the array, we iterate over all possible values of j and update dp[i][j].

   a. dp[i][j+nums[i-1]] += dp[i-1][j]

   This means if we add nums[i-1] to include current element in the sum, then the required target becomes j+nums[i-1]
   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 i-1 elements to the dp[i][j+nums[i-1]].
   

   b. dp[i][j-nums[i-1]] += dp[i-1][j]

   This means if we subtract nums[i-1] to include current element in the sum, then the required target becomes j-nums[i-1] 
   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 i-1 elements to the dp[i][j-nums[i-1]].
   

4. 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[i-1] < 2*sum+1) dp[i][j] += dp[i-1][j+nums[i-1]]; if (j-nums[i-1] >= 0) dp[i][j] += dp[i-1][j-nums[i-1]]; } } 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.

1