Getting all possible sums that add up to a given number

Question

I'm making an math app for the android. In one of these fields the user can enter an int (no digits and above 0). The idea is to get all possible sums that make this int, without doubles (4+1 == 1+4 in this case). The only thing known is this one int.

For example:

Say the user enters 4, I would like the app to return:

• 4
• 3+1
• 2+2
• 2+1+1
• 1+1+1+1

Obviously 4 == 4 so that should be added too. Any suggestions as to how i should go about doing this?

Answer 1

Here's a simple algorithm that purports to do that

from : http://introcs.cs.princeton.edu/java/23recursion/Partition.java.html

public class Partition { 

    public static void partition(int n) {
        partition(n, n, "");
    }
    public static void partition(int n, int max, String prefix) {
        if (n == 0) {
            StdOut.println(prefix);
            return;
        }

        for (int i = Math.min(max, n); i >= 1; i--) {
            partition(n-i, i, prefix + " " + i);
        }
    }


    public static void main(String[] args) { 
        int N = Integer.parseInt(args[0]);
        partition(N);
    }

}