Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# dongr0510/subset_sum_bottom_up.py

Last active Sep 8, 2020
 def can_partition(num, sum): n = len(num) dp = [[False for x in range(sum+1)] for y in range(n)] # populate the sum = 0 columns, as we can always form '0' sum with an empty set 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 s in range(1, sum+1): dp[s] = True if num == s else False # process all subsets for all sums for i in range(1, n): for s in range(1, sum+1): # if we can get the sum 's' without the number at index 'i' if dp[i - 1][s]: dp[i][s] = dp[i - 1][s] elif s >= num[i]: # else include the number and see if we can find a subset to get the remaining sum dp[i][s] = dp[i - 1][s - num[i]] # the bottom-right corner will have our answer. return dp[n - 1][sum] # decrease space simplicity def can_partition(num, sum): n = len(num) dp = [False for x in range(sum+1)] # handle sum=0, as we can always have '0' sum with an empty set dp = True # with only one number, we can have a subset only when the required sum is equal to its value for s in range(1, sum+1): dp[s] = num == s # process all subsets for all sums for i in range(1, n): for s in range(sum, -1, -1): # if dp[s]==true, this means we can get the sum 's' without num[i], hence we can move on to # the next number else we can include num[i] and see if we can find a subset to get the # remaining sum if not dp[s] and s >= num[i]: dp[s] = dp[s - num[i]] return dp[sum]
to join this conversation on GitHub. Already have an account? Sign in to comment