Skip to content

Instantly share code, notes, and snippets.

@dongr0510
Created September 8, 2020 23:31
Show Gist options
  • Save dongr0510/adb333b63e5fc2926f2d6e0bdc0a370b to your computer and use it in GitHub Desktop.
Save dongr0510/adb333b63e5fc2926f2d6e0bdc0a370b to your computer and use it in GitHub Desktop.
def count_subsets(num, sum):
n = len(num)
dp = [[-1 for x in range(sum+1)] for y in range(n)]
# populate the sum = 0 columns, as we will always have an empty set for zero sum
for i in range(0, n):
dp[i][0] = 1
# with only one number, we can form a subset only when the required sum is
# equal to its value
for s in range(1, sum+1):
dp[0][s] = 1 if num[0] == s else 0
# process all subsets for all sums
for i in range(1, n):
for s in range(1, sum+1):
# exclude the number
dp[i][s] = dp[i - 1][s]
# include the number, if it does not exceed the sum
if s >= num[i]:
dp[i][s] += dp[i - 1][s - num[i]]
# the bottom-right corner will have our answer.
return dp[n - 1][sum]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment