Partition a number. For example, partition(5) = [ [5], [4,1], [3,2], [3,1,1], [2,2,1], [2,1,1,1], [1,1,1,1,1] ]. For more information on partions, see http://en.wikipedia.org/wiki/Partition_(number_theory)

Partition.java

package com.seanpont.partition;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * User: sean
 * Date: 5/23/13
 */
public class Partition {

    /**
     * partition returns a list of int[] that represent all distinct partitions of n.
     */
    public static List<int[]> partition(int n) {
        //create a place to store partial solutions
        List<Integer> partial = new ArrayList<Integer>();

        //create place to store complete solutions
        List<int[]> partitions = new ArrayList<int[]>();

        //kick off the partitioning
        partition(n, partial, partitions);

        //return the results
        return partitions;
    }

    /**
     * This is the meat of the hamburger.
     * If n=0, it copies the partial solution into the list of complete solutions.
     * Else, for all values i less than or equal to n, it puts i in the partial solution and partitions the remainder n-i.
     */
    private static void partition(int n, List<Integer> partial, List<int[]> partitions) {
        //System.out.println("partition " + n + ", partial solution: " + partial);
        if (n == 0) {
            //complete solution is held in 'partial' --> add it to list of solutions
            partitions.add(toArray(partial));
        } else {
            // Iterate through all numbers i less than n. For each one, add 'i' to the list of partial solutions,
            // and partition the remainder given this partial solution.
            // For example, if n=5, it will call p(0, [5]), p(1, [4]), p(2, [3]) and p(1, [4])
            // It avoids duplicate solutions by ensuring that the partial array is always non-increasing
            for (int i=n; i>0; i--) {
                if (partial.isEmpty() || partial.get(partial.size()-1) >= i) {
                    //add i to the list of partial solutions
                    partial.add(i);
                    //partition the remainder given the partial solution
                    partition(n-i, partial, partitions);
                    //remove i from the partial solution
                    partial.remove(partial.size()-1);
                }
            }
        }
    }

    /**
     * Helper method: creates a new integer array and copies the contents of the list into the array.
     */
    static int[] toArray(List<Integer> list) {
        int i = 0;
        int[] arr = new int[list.size()];
        for (int val : list) {
            arr[i++] = val;
        }
        return arr;
    }

    /**
     * This is the main method. It takes a number from the command line, partitions it, and prints the results.
     */
    public static void main(String[] args) throws IOException {
        //ask what number to partition
        System.out.print("enter number to partition: ");

        //read the input from the console.
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String line = reader.readLine();
        int input = new Integer(line);

        //partition the number
        List<int[]> partitions = partition(input);

        //print the result
        System.out.println("\npartitions of " + input + ":");
        for (int[] partition : partitions) {
            System.out.println(Arrays.toString(partition));
        }
    }
}