Integer Partition

Question

The aim is to enumerate all possible sets of whole numbers whose sum is a given integer.

class partition
{
    public static void main(String[] ar)
    {
        part(66);
    }

    public static void part(int n)
    {
        part(n,1,"");
    }

    public static void part(int n, int st, String prefix)
    {
        if(n == 0)
        {
            System.out.println(prefix.substring(1));
            return;
        }
        for(int i = st; i <= n; i++)
            part(n-i,i,prefix + " " + i);
    }
}

Please help to improve my code and suggest a better solution.

Answer 1

My first observation is that your variable names mean nothing. n and st should describe what they are supposed to represent.

I don't like having the println in the part function. In my opinion, the value should be returned back up the stack and printed in the user interface layer. Please see Separation of Concerns for more information. This will allow your code to be followed a little easier.

Other than that, not too many other things to note.

Answer 2

This program finds all combinations of numbers that add up to a specified number (66). There are a number of things that I dislike about it.

1. Using String concatenation in a tight loop is a poor choice when it comes to performance. This statement prefix + " " + i has to go.
2. the variable names in your loop are almost meaningless.
3. You are using a String prefix as if it is a Stack (adding a value to the String in the loop). Since most combinations are not going to add to the target it seems like a lot of String manipulation to get there.
4. the recursive method should not be public.
5. Java classes should be named with a capital letter, i.e. it should be Partition.

Using a Stack (really, a Deque - or ArrayDeque ) would ba a typical choice, but in this case, I feel that converting the primitive int values to an Integer would be unnecessary. Using an int[] array would be simple enough.... especially because there is an upper-bound on the stack size.

So, taking that all in to account, I would suggest the following changes:

1. the part(int) (renamed to partition) should construct an int[] array as a stack. It should then call the recursive method.
2. the recursive method should only construct the String value for actual results, not intermediate results.
3. rename the variables (and methods) to be more descriptive.
4. used 'final' where I can to show what variables cannot change, and it can help with the JIT Optimization.

The refactor would end up looking like:

public static void main(String[] ar)
{
    partition(66);
}

public static void partition(final int n)
{
    recursivePartition(n, 1, new int[n], 0);
}

private static void recursivePartition(final int target, final int from, final int[] stack, final int stacksize)
{
    if(target == 0) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < stacksize; i++) {
            sb.append(stack[i]).append(" ");
        }
        System.out.println(sb.toString());
        return;
    }
    for(int i = from; i <= target; i++) {
        stack[stacksize] = i;
        recursivePartition(target-i, i, stack, stacksize + 1);
    }
}