Similar Problems

Similar Problems not available

Target Sum - Leetcode Solution

LeetCode:  Target Sum Leetcode Solution

Difficulty: Medium

Topics: backtracking array dynamic-programming  

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.

Target Sum Solution Code

1You 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.
2
3Find out how many ways to assign symbols to make sum of integers equal to target S.
4
5Example 1:
6Input: nums is [1, 1, 1, 1, 1], S is 3. 
7Output: 5
8Explanation: 
9
10-1+1+1+1+1 = 3
11+1-1+1+1+1 = 3
12+1+1-1+1+1 = 3
13+1+1+1-1+1 = 3
14+1+1+1+1-1 = 3
15
16There are 5 ways to assign symbols to make the sum of nums be target 3.
17 
18
19Constraints:
20The length of the given array is positive and will not exceed 20.
21The sum of elements in the given array will not exceed 1000.
22Your output answer is guaranteed to be fitted in a 32-bit integer.