Skip to content

Instantly share code, notes, and snippets.

@dongr0510
Created September 8, 2020 18:35
Show Gist options
  • Save dongr0510/b0b776bc657e30a3a06baf54b1c31dbd to your computer and use it in GitHub Desktop.
Save dongr0510/b0b776bc657e30a3a06baf54b1c31dbd to your computer and use it in GitHub Desktop.
for each number 'i'
add number 'i' to S1 and recursively process the remaining numbers
add number 'i' to S2 and recursively process the remaining numbers
return the minimum absolute difference of the above two sets
def can_partition(num):
return can_partition_recursive(num, 0, 0, 0)
def can_partition_recursive(num, currentIndex, sum1, sum2):
# base check
if currentIndex == len(num):
return abs(sum1 - sum2)
# recursive call after including the number at the currentIndex in the first set
diff1 = can_partition_recursive(
num, currentIndex + 1, sum1 + num[currentIndex], sum2)
# recursive call after including the number at the currentIndex in the second set
diff2 = can_partition_recursive(
num, currentIndex + 1, sum1, sum2 + num[currentIndex])
return min(diff1, diff2)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment