Grokking Dynamic Programming Patterns for Coding Interviews

0% completed

​

Count of Subset Sum

Problem Statement

Try it yourself

Problem Statement

Given a set of positive numbers, find the total number of subsets whose sum is equal to a given number 'S'.

Example 1:

Input: {1, 1, 2, 3}, S=4
Output: 3
The given set has '3' subsets whose sum is '4': {1, 1, 2}, {1, 3}, {1, 3}
Note that we have two similar sets {1, 3}, because we have two '1' in our input.

Example 2:

Input: {1, 2, 7, 1, 5}, S=9
Output: 3
The given set has '3' subsets whose sum is '9': {2, 7}, {1, 7, 1}, {1, 2, 1, 5}

Try it yourself

Try solving this question here:

Python3
Python3
. . . .
Mark as Completed
R

Ray

· 4 years ago

For "Top-down Dynamic Programming with Memoization", is there a good explanation on using the currentIndex as key first, then sum as key? Why currentIndex should be first?

The alternative would be to use sum as first key and then currentIndex as key.

Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

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

      if acc == s:
        return 1

      if index == len(num):
        return 0 

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

      return result
      
    return dp(0, 0, {})
Online Courses

Online Courses

· 4 months ago

My solution (from memoization to 1D tabular DP):

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

    def subsets(idx, current_sum):
      if current_sum == sum1:
        return 1
      
      if idx == n or current_sum > sum1:
        return 0 
      
      key = (idx, current_sum)
      if key in memo:
        return memo[key]
      
      # skip
      r1 = subsets(idx + 1, current_sum)

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

      result = r1 + r2
      memo[key] = result
      
      return result
    
    count = subsets(0, 0)

    return count
  
  def countSubsets(self, num, sum1):
    n = len(num)
    if n == 0:
      return 0
    
    # state
    dp = [0] * (sum1 +

On This Page

Problem Statement

Try it yourself