Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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][0] = 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[0][s] = True if num[0] == 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[0] = 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[0] == 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]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment