Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# dongr0510/equal_partition_bottom_up.py

Created Sep 8, 2020
 def can_partition(num): s = sum(num) # if 's' is a an odd number, we can't have two subsets with same total if s % 2 != 0: return False # we are trying to find a subset of given numbers that has a total sum of 's/2'. s = int(s / 2) n = len(num) dp = [[False for x in range(s+1)] for y in range(n)] # populate the sum=0 column, as we can always have '0' sum without including # any element for i in range(0, n): dp[i] = True # with only one number, we can form a subset only when the required sum is # equal to its value for j in range(1, s+1): dp[j] = num == j # process all subsets for all sums for i in range(1, n): for j in range(1, s+1): # if we can get the sum 'j' without the number at index 'i' if dp[i - 1][j]: dp[i][j] = dp[i - 1][j] elif j >= num[i]: # else if we can find a subset to get the remaining sum dp[i][j] = dp[i - 1][j - num[i]] # the bottom-right corner will have our answer. return dp[n - 1][s]
to join this conversation on GitHub. Already have an account? Sign in to comment