Optimizing unique partitions of integers

I am working on a project involving the unique partitioning of integers. I.e. I am looking to have all of the partitions of n = x1 + x2 + x3 + ... + xk, where xi = xj implies i = j.

For example, if I give my code input of 10, I want to have as output (in an ArrayList>) the following:

[[1, 2, 3, 4], [2, 3, 5], [1, 4, 5], [1, 3, 6], [4, 6], [1, 2, 7], [3, 7], [2, 8], [1, 9], [10]]

Note that I don't have [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], etc. because these have duplicate entries.

The problem is, once I try to get all of the unique partitions of numbers greater than 70 or so, it starts to take a noticeable amount of time. Further, this shouldn't be a particularly slow algorithm.

The class is below:

```
import java.math.*;
import java.util.*;

public class UniquePartition {

private BigInteger n;
private ArrayList> allPartitions;

//Constructs the object with integer. Sets the target and then calculates partitions.
public UniquePartition(int num) {
n = new BigInteger(String.valueOf(num));
allPartitions = new ArrayList>();
allPartitions = findPartitions();
}

//Constructs the object. Sets the target and then calculates partitions.
public UniquePartition(BigInteger num) {
n = num;
allPartitions = new ArrayList>();
allPartitions = findPartitions();
}

//Returns partitions without calculating them.
public ArrayList> getPartitions() {
return allPartitions;
}

//Returns the nth partition without calculating them.
public ArrayList getPartitionN(int n) {
// ArrayList> partitions = new ArrayList>();
return allPartitions.get(n);
}

// Returns an ArrayList containing ArrayLists, each of which is a single partition. Should never be called, otherwise
// will redo calculation.
public ArrayList> findPartitions() {
ArrayList pS = new ArrayList();
pS = findPartitions(pS,n,n,"");

for(int i=0;i partition = new ArrayList()

Yes, it is unreasonable to expect this approach to be "fast".

This answer will focus on... drumroll, please!
Why your current approach is slow

The reason for why it is unreasonable to expect this approach to be fast can be shown simply by adding a private int calls; field to your class and increasing it at the beginning of your findPartitions(ArrayList p, BigInteger target, BigInteger maxValue, String suffix) method. Then log this value for different values in your main method.

Value 5 Calls: 20
Value 10 Calls: 103
Value 15 Calls: 333
Value 20 Calls: 896
Value 25 Calls: 2141
Value 30 Calls: 4735
Value 35 Calls: 9877
Value 40 Calls: 19679
Value 45 Calls: 37729
Value 50 Calls: 70073
Value 55 Calls: 126586
Value 60 Calls: 223195

As you can see, the number of calls to the method increases dramatically, of exponential order.

This is because you are using a recursive approach to the problem that often creates a new "branch".

So, how to speed this up?

Let's take a look at some of the output for the value 20:

2 3 7 8 
1 4 7 8 
5 7 8 
2 3 6 9 
1 4 6 9 
5 6 9 
2 3 5 10 
1 4 5 10 
2 3 4 11 
4 5 11 
2 3 15 
1 4 15 
5 15

What do all these have in common? They all can make the value 5 in there some where. 11 + 4 (= 15) + 3 + 2 (= 5).

So, what do I want to say with this?

Once you have calculated the possible partitions for the value of 5, reuse them!

To accomplish this you can use a Map> structure. In your findPartitions method, check if the map contains a value for target (map.containsKey) and if it does then reuse it. If it does not, then do something similar to what you are doing there already and use map.put at the end to add the found values to the map.

I have to warn you though that even adding this reusing-feature, I still expect it to take quite a long time for larger numbers.

I strongly suggest that you switch back to using int (or Integer for storing them in collections). An int will take you to 2 147 483 647, try partitioning that number first before switching to BigInteger (Hint hint: It will still take a tremendous amount of time to partition 2 147 483 647, if you don't believe me then try doing it by hand).

StackExchange Code Review Q#45910, answer score: 11