Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Problem Challenge 2: Target Sum (hard)

Problem Statement

You are given a set of positive numbers and a target sum ‘S’. Each number should be assigned either a ‘+’ or ‘-’ sign. We need to find the total ways to assign symbols to make the sum of the numbers equal to the target ‘S’.

Example 1:

Input: {1, 1, 2, 3}, S=1
Output: 3
Explanation: The given set has '3' ways to make a sum of '1': {+1-1-2+3} & {-1+1-2+3} & {+1+1+2-3}

Example 2:

Input: {1, 2, 7, 1}, S=9
Output: 2
Explanation: The given set has '2' ways to make a sum of '9': {+1+2+7-1} & {-1+2+7+1}

Constraints:

  • 1 <= num.length <= 20

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Avinash Agarwal

· 4 years ago

This is the wrong solution to the problem. The right solution is below,

public int findTargetSumWays(int[] nums, int S) { int total = Arrays.stream(nums).sum(); int[] dp = new int[2 * total + 1]; dp[nums[0] + total] = 1; dp[-nums[0] + total] += 1;

for (int i = 1; i < nums.length; i++) { int[] next = new int[2 * total + 1]; for (int sum = -total; sum 0) { next[sum + nums[i] + total] += dp[sum + total]; next[sum - nums[i] + total] += dp[sum + total]; } } dp = next; }

return Math.abs(S) > total ? 0 : dp[S + total]; }

Show 1 reply
C

Charlotte

· 4 years ago

This method cannot past the test case [0,0,0,0,0,0,0,0,1] S = 1 . Is there another solution?

Show 2 replies
G

Gaurav Sisodiya

· 4 years ago

Can you share the Target Sum solution with memoization?