Grokking Dynamic Programming Patterns for Coding Interviews
Vote

0% completed

​

Target Sum

Problem Statement

Example 1:

Example 2:

Try it yourself

Problem Statement

Given a set of positive numbers (non zero) and a target sum 'S'. Each number should be assigned either a '+' or '-' sign. We need to find out total ways to assign symbols to make the sum of numbers equal to 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
  • 0 <= nums[i] <= 1000
  • 0 <= sum(nums[i]) <= 1000
  • -1000 <= target <= 1000

Try it yourself

Try solving this question here:

Python3
Python3
. . . .
A

Anonymous

· 2 years ago

class Solution:
  def findTargetSubsets(self, num, s):
    def dp(index, acc, memo):
      
      if (index, acc) in memo:
        return memo[(index, acc)]

      if index == len(num) and acc == s:
        return 1

      if index == len(num) and acc != s:
        return 0

      result = dp(index + 1, acc + num[index], memo) + dp(index + 1, acc - num[index], memo)

      memo[(index, acc)] = result
  
      return result

    return dp(0, 0, {})
A

Anonymous

· 4 years ago

Can we use the logic from "minimum difference between subsets" ? We can convert this problem to find the number of subsets which has the target as "sum(nums) - S".

Or am I missing something?

A

Anonymous

· 5 years ago

There seems to be a typo somewhere in the code. When I tried the same algorithm with Leetcode I get the wrong answer. https://leetcode.com/problems/target-sum/

Show 2 replies

Reading Progress

0%

Vote for new content

On This Page

Problem Statement

Example 1:

Example 2:

Try it yourself