Question

How to find all possible ways to write a positive integer as a sum of positive integers in Python

Answer 1

# Print a partition stored in 'arr' in the form "a + b + c"
def print_array(arr, size):
    for i in range(size):
        if i > 0:
            print(" + ", end="")   # add plus signs between numbers
        print(arr[i], end="")
    print()


"""
    Generate all partitions of a number using non-decreasing sequences.

    arr       – current partial partition being built
    size      – how many elements are currently in arr
    start     – the smallest number allowed next (prevents duplicates like 2+1 vs 1+2)
    remaining – how much is left to reach the target sum

    When remaining == 0, arr contains a complete valid partition.
"""
def partitions(arr, size, start, remaining):

    # Base case: exact sum reached
    if remaining == 0:
        if size >= 2:      # enforce "two or more integers"
            print_array(arr, size)
        return

    # Try all next values from 'start' up to 'remaining'
    for j in range(start, remaining + 1):
        arr[size] = j                          # choose j
        partitions(arr, size + 1, j, remaining - j)  # recurse with reduced remainder
        # no need to "pop" in Python; we just overwrite next time


def main():
    n = 5                 # number to partition
    arr = [0] * 128       # holds current partition (large enough buffer)

    partitions(arr, 0, 1, n)  # start with smallest allowed value = 1


main()


"""
run:

1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 2
1 + 1 + 3
1 + 2 + 2
1 + 4
2 + 3

"""

 

70+ SQL courses for beginners and professionals

Answer 2

"""
Generate all ways to write a positive integer n
as a sum of positive integers (integer partitions).

Example for n = 5:
[
  [5],
  [4, 1],
  [3, 2],
  [3, 1, 1],
  [2, 2, 1],
  [2, 1, 1, 1],
  [1, 1, 1, 1, 1]
]
"""

def partitions(n):
    """
    Return all partitions of a positive integer n.
    Each partition is a list of integers in non-increasing order.
    """
    results = []

    def backtrack(remaining, max_value, current):
        # If nothing remains, we found a valid partition
        if remaining == 0:
            results.append(current.copy())
            return

        # Try next numbers from max_value down to 1
        for next_value in range(min(remaining, max_value), 0, -1):
            current.append(next_value)                 # choose
            backtrack(remaining - next_value, next_value, current)  # explore
            current.pop()                              # un-choose (backtrack)

    backtrack(n, n, [])
    return results


# Run the program:
result = partitions(5)
print(result)


"""
run:

[[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]]

"""

 

70+ SQL courses for beginners and professionals