Skip to content

Instantly share code, notes, and snippets.

Created September 8, 2020 23:24
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save dongr0510/299d4f0f0b5b3d6b92999c5209d39691 to your computer and use it in GitHub Desktop.
def count_subsets(num, sum):
# create a two dimensional array for Memoization, each element is initialized to '-1'
dp = [[-1 for x in range(sum+1)] for y in range(len(num))]
return count_subsets_recursive(dp, num, sum, 0)
def count_subsets_recursive(dp, num, sum, currentIndex):
# base checks
if sum == 0:
return 1
n = len(num)
if n == 0 or currentIndex >= n:
return 0
# check if we have not already processed a similar problem
if dp[currentIndex][sum] == -1:
# recursive call after choosing the number at the currentIndex
# if the number at currentIndex exceeds the sum, we shouldn't process this
sum1 = 0
if num[currentIndex] <= sum:
sum1 = count_subsets_recursive(
dp, num, sum - num[currentIndex], currentIndex + 1)
# recursive call after excluding the number at the currentIndex
sum2 = count_subsets_recursive(dp, num, sum, currentIndex + 1)
dp[currentIndex][sum] = sum1 + sum2
return dp[currentIndex][sum]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment