Question

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

Answer 1

// Print a partition stored in 'arr' in the form "a + b + c"
public class Main {

    static void printArray(int[] arr, int size) {
        for (int i = 0; i < size; i++) {
            if (i > 0) System.out.print(" + ");   // add plus signs between numbers
            System.out.print(arr[i]);
        }
        System.out.println();
    }

    /**
        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.
    */
    static void partitions(int[] arr, int size, int start, int remaining) {
        // 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 (int 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 Java; we just overwrite next time
        }
    }

    public static void main(String[] args) {
        int n = 5;                 // number to partition
        int[] arr = new 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

import java.util.ArrayList;
import java.util.List;

public class IntegerPartitions {

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

    // Function that returns all partitions of n
    public static List<List<Integer>> partitions(int n) {
        List<List<Integer>> results = new ArrayList<>();
        backtrack(n, n, new ArrayList<>(), results);
        
        return results;
    }

    /**
     * Backtracking helper function.
     *
     * @param remaining how much is left to reach n
     * @param max       maximum allowed next number (keeps order non-increasing)
     * @param current   current partial partition
     * @param results   list of all partitions
     */
    private static void backtrack(int remaining, int max, List<Integer> current, List<List<Integer>> results) {
        // If nothing remains, we found a valid partition
        if (remaining == 0) {
            results.add(new ArrayList<>(current));
            return;
        }

        // Try next numbers from max down to 1
        for (int next = Math.min(remaining, max); next >= 1; next--) {
            current.add(next);                         // choose
            backtrack(remaining - next, next, current, results); // explore
            current.remove(current.size() - 1);        // un-choose (backtrack)
        }
    }

    public static void main(String[] args) {
        List<List<Integer>> result = partitions(5);
        
        System.out.println(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