marksteve · August 15, 2016 17:14 · Aug 15, 2016 · Aug 15, 2016
diff --git a/partition.py b/partition.py
@@ -0,0 +1,36 @@
+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))
No results found