Question

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

Answer 1

package main

import (
    "fmt"
)

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

    for i := 0; i < size; i++ {
        if i > 0 {
            line += " + "   // add plus signs between numbers
        }
        line += fmt.Sprintf("%d", arr[i])
    }

    fmt.Println(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 []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'
    for j := start; j <= remaining; j++ {
        arr[size] = j                          // choose j
        partitions(arr, size+1, j, remaining-j) // recurse with reduced remainder
        // no need to "pop" in Go; we just overwrite next time
    }
}

func main() {
    n := 5                     // number to partition
    arr := make([]int, 128)    // holds current partition (large enough buffer)

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



/*
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

package main

import (
    "fmt"
)

// partitions returns all ways to write n as a sum of positive integers.
// Each partition is non‑decreasing (e.g., [1 2 2], not [2 1 2]).
func partitions(n int) [][]int {
    var result [][]int   // stores all completed partitions
    var current []int    // current partial partition being built

    // backtrack recursively builds partitions.
    // remaining — how much is left to reach n
    // start — the minimum next value allowed (enforces non‑decreasing order)
    var backtrack func(remaining, start int)
    backtrack = func(remaining, start int) {
        // If nothing is left, we found a valid partition
        if remaining == 0 {
            // Copy current slice because it will be modified later
            comb := make([]int, len(current))
            copy(comb, current)
            result = append(result, comb)
            return
        }

        // Try all possible next values from `start` up to `remaining`
        for i := start; i <= remaining; i++ {
            current = append(current, i)     // choose i
            backtrack(remaining-i, i)        // recurse with reduced remainder
            current = current[:len(current)-1] // undo the choice (backtrack)
        }
    }

    // Start building partitions with minimum allowed value = 1
    backtrack(n, 1)
    return result
}

func main() {
    n := 5
    for _, p := range partitions(n) {
        fmt.Println(p)
    }
}


/*
run:

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

*/

 

70+ SQL courses for beginners and professionals