# Partition

In number theory and combinatorics, a partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition. If order matters, the sum becomes a composition. For example, 4 can be partitioned in five distinct ways:

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

The order-dependent composition 1 + 3 is the same partition as 3 + 1, while 1 + 2 + 1 and 1 + 1 + 2 are the same partition as 2 + 1 + 1. If we have a partition of n, we can reduce it to a partition of n-1 in a canonical way by subtracting one from the smallest item in the partition. E.g. 1+2+3 => 2+3, 2+4 => 1+4. This algorithm reverses the process: for each partition p of n-1, it finds the partitions of n that would be reduced to p by this process. Therefore, each partition of n is output exactly once, at the step when the partition of n-1 to which it reduces is considered.

```public class Partition {
public static void partition(int n) {
partition(n, n, "");
}
public static void partition(int n, int max, String answer) {
if (n == 0) {
return;
}
for (int i = Math.min(max, n); i >= 1; i--) {
partition(n-i, i, answer + "+" + i);
}
}
public static void main(String[] args) {
int N = 4;
partition(N);
}
}```

The purpose of the substring() function on line number 7 is to remove the ‘+’ sign at beginning of each line of output. As usual, the main function has purposely been kept to minimum and its expected that students will write appropriate input/output statements as per the requirement.

## 3 thoughts on “Partition”

1. Mayank Singh

you can trip extra buffer “max”, below way, also fetches the same solution and its slightly more readable….your thoughts?

```    public static void partition(int n, String answer) {
if (n == 0) {
return;
}
for (int i = n; i >= 1; i--) {
partition(n-i, answer + "+" + i);
}
}
public static void main(String[] args) {
int n = 5;
partition(n,"");
}
```
1. Vinay Singh Post author

I agree that it’s slightly more readable and would save a bit of memory as well, but, it would be slightly more expensive in terms of time also.
I modified both the recursive version to add a counter as follows:

#### With max

```public class PartitionRecrusive {
private static int c = 0;
public static void partition(int n) {
partition(n, n, "");
}
public static void partition(int n, int max, String prefix) {
if (n == 0) {
System.out.println(prefix.substring(1));
return;
}
for (int i = Math.min(max, n); i >= 1; i--) {
c=c+1;
partition(n-i, i, prefix + "+" + i);
}
}
public static void main(String[] args) {
int N = 4;
partition(N);
System.out.println(c);
}
}

```

#### Without max

```class Partition{
public static int c=0;
public static void partition(int n, String answer) {
if (n == 0) {
return;
}
for (int i = n; i >= 1; i--) {
c++;
partition(n-i, answer + "+" + i);
}
}

public static void main(String[] args) {
int n = 5;
partition(n,"");
System.out.println(c);

}
}```

The one with max gave 11 and the without max gave 33.
It may seem clichéd but you can’t optimize time and space at the same time! 🙂

2. Mayank Singh

yeah..later found that adding “max” also helps in chucking dupes!! 🙂

This site uses Akismet to reduce spam. Learn how your comment data is processed.