Question

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

Answer 1

// Print a partition stored in 'arr' in the form "a + b + c"
func printArray(_ arr: [Int], _ size: Int) {
    var line = ""

    for i in 0..<size {
        if i > 0 {
            line += " + "   // add plus signs between numbers
        }
        line += "\(arr[i])"
    }

    print(line)
}

/*
    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.
*/
func partitions(_ arr: inout [Int], _ size: Int, _ start: Int, _ remaining: Int) {

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

    // Try all next values from 'start' up to 'remaining'
    if start > remaining {
        return   // avoid invalid range
    }
    
    for j in start...remaining {
        arr[size] = j                          // choose j
        partitions(&arr, size + 1, j, remaining - j)  // recurse with reduced remainder
        // no need to "pop" in Swift; we just overwrite next time
    }
}

func main() {
    let n = 5                 // number to partition
    var arr = Array(repeating: 0, count: 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

import Foundation

/// Generate all ways to write `n` as a sum of positive integers.
/// Example: n = 4 → [1+1+1+1], [1+1+2], [2+2], [1+3], [4]
///
/// - Parameters:
///   - n: The target number to partition.
///   - maxValue: The largest allowed value in the current step (prevents duplicates).
///   - current: The partial partition being built.
///   - result: The final list of all partitions.
func generatePartitions(
    _ n: Int,
    maxValue: Int,
    current: inout [Int],
    result: inout [[Int]]
) {
    // Base case: if n reaches 0, we found a valid partition
    if n == 0 {
        result.append(current)
        return
    }

    // Try all values from min(n, maxValue) down to 1
    for value in stride(from: min(n, maxValue), through: 1, by: -1) {
        // Choose this value
        current.append(value)

        // Recurse with reduced n and updated maxValue
        generatePartitions(n - value, maxValue: value, current: &current, result: &result)

        // Backtrack: remove last value and try next
        current.removeLast()
    }
}

/// Public function to get all partitions of a number.
func partitions(of n: Int) -> [[Int]] {
    var result: [[Int]] = []
    var current: [Int] = []
    generatePartitions(n, maxValue: n, current: &current, result: &result)
    return result
}


let n = 5
let all = partitions(of: n)
print("Partitions of \(n):")
for p in all {
    print(p)
}



/*
run:

Partitions of 5:
[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