Skip to content

Instantly share code, notes, and snippets.

@marksteve
Last active August 15, 2016 17:14
Show Gist options
  • Save marksteve/0bfeee29fe93b86ffe901fdfd420fe41 to your computer and use it in GitHub Desktop.
Save marksteve/0bfeee29fe93b86ffe901fdfd420fe41 to your computer and use it in GitHub Desktop.
import itertools
def partition(n):
x = 1
_sum = 0
# Get possible addends
addends = set()
while _sum < n:
addends.add(x)
_sum += x
x += 1
addends.add(x)
# Get all combinations
choices = set()
for t in range(len(addends)):
for combination in itertools.combinations(addends, t):
if sum(combination) == n:
choices.add(combination)
# Get first combination with most addends
result = None
max_len = 0
for choice in choices:
if len(choice) > max_len:
max_len = len(choice)
result = choice
return result
if __name__ == '__main__':
s = int(raw_input())
print list(partition(s))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment