Grokking Dynamic Programming Patterns for Coding Interviews
Vote

0% completed

​

Solution: Target Sum

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

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Alan Lo

· 4 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
M

Meghana

· 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?

Mohammed Dh Abbas

Mohammed Dh Abbas

· 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, {})
Online Courses

Online Courses

· 5 months ago

My version, from memoization to DP:

class Solution:
  def findTargetSubsets_memoize(self, num, s):
    n = len(num)
    if n == 0:
      return 0
    
    memo = {}

    def subsets(idx, current_sum):
      if idx == n:
        return 1 if current_sum == s else 0
      
      key = (idx, current_sum)
      if key in memo:
        return memo[key]

      # plus
      plus = subsets(idx + 1, current_sum + num[idx])

      # minus
      minus = subsets(idx + 1, current_sum - num[idx])

      result = plus + minus
      memo[key] = result

      return result
    
    return subsets(0, 0)

  def findTargetSubsets(self, num, s):
    n = len(num)
    if n == 0:
      return 0

    total = sum(num)
    if abs(s) > total:
      return 0

    # Note: we either add or sub in the mem