Grokking Dynamic Programming Patterns for Coding Interviews
Vote

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
. . . .
A

Anonymous

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

Anonymous

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

Reading Progress

0%

Vote for new content

On This Page

Problem Statement

Try it yourself