Skip to content

Instantly share code, notes, and snippets.

Created September 8, 2020 22:40
  • 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
What would you like to do?
def can_partition(num):
s = sum(num)
n = len(num)
dp = [[False for x in range(int(s/2)+1)] for y in range(n)]
# populate the s=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 that number
for j in range(0, int(s/2)+1):
dp[0][j] = num[0] == j
# process all subsets for all sums
for i in range(1, n):
for j in range(1, int(s/2)+1):
if dp[n-1][j]:
dp[i][j] = dp[i-1][j]
elif j>=num[i]:
# else include the number and see if we can find a subset to get the remaining sum
dp[i][j] = dp[i-1][j - num[i]]
sum1 = 0
for i in range(int(s/2), -1, -1):
if dp[n-1][i]:
sum1 = i
sum2 = s - sum1
return abs(sum2-sum1)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment