Question

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

Answer 1

// Print a partition stored in 'arr' in the form "a + b + c"
fun printArray(arr: IntArray, size: Int) {
    val sb = StringBuilder()

    for (i in 0 until size) {
        if (i > 0) sb.append(" + ")   // add plus signs between numbers
        sb.append(arr[i])
    }

    println(sb.toString())
}

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

fun main() {
    val n: Int = 5                 // number to partition
    val arr = IntArray(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

/**
 * Returns all partitions of a positive integer n.
 * A partition is represented as a list of integers in non-increasing order.
 */
fun partitions(n: Int): List<List<Int>> {

    /**
     * Recursive helper:
     * remaining  – how much is left to partition
     * maxAllowed – the largest number we may use next (keeps order non-increasing)
     */
    fun generate(remaining: Int, maxAllowed: Int): List<List<Int>> {
        if (remaining == 0) {
            // One valid partition: empty list (base case)
            return listOf(emptyList())
        }

        val result = mutableListOf<List<Int>>()

        // Try all possible next values k from maxAllowed down to 1
        for (k in maxAllowed downTo 1) {
            if (k <= remaining) {
                // Recursively partition the remainder
                val subPartitions = generate(remaining - k, k)

                // Prepend k to each sub-partition
                for (p in subPartitions) {
                    result.add(listOf(k) + p)
                }
            }
        }

        return result
    }

    return generate(n, n)
}

fun main() {
    val n = 5
    println("Partitions of $n:")
    
    partitions(n).forEach { println(it.joinToString(" + ")) }
}



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