0% completed

Solution: Count of Subset Sum

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}

Basic Solution

This problem follows the 0/1 Knapsack pattern and is quite similar to "Subset Sum"

.....

Like the course? Get enrolled and start learning!

Online Courses

· 5 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 +

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

R

Ray

· 4 years ago

Reading Progress

0%