def can_partition(num):
total = sum(num)
half = total // 2
dp = [[True] + [False] * half for _ in range(len(num))]
if num[0] <= half:
dp[0][num[0]] = True
for i in range(1, len(num)):
for j in range (1, half + 1):
if num[i] <= j:
dp[i][j] = dp[i-1][j] or dp[i-1][j - num[i]]
else:
dp[i][j] = dp[i - 1][j]
for j in range(half, -1, -1):
if dp[len(num) - 1][j]:
return total - j - j
Any thoughts?
Type your question above this line.
Course: https://www.educative.io/collection/5668639101419520/5671464854355968
Lesson: https://www.educative.io/collection/page/5668639101419520/5671464854355968/5390739594805248
