Integer Partition With Distinct Parts
How many ways can you write an integer
n as the sum of a decreasing sequence(excluding
Let’s look at an example from Wikipedia:
Alternatively, we could count partitions in which no number occurs more than once. Such a partition is called a partition with distinct parts. If we count the partitions of 8 with distinct parts, we also obtain 6:
- 7 + 1
- 6 + 2
- 5 + 3
- 5 + 2 + 1
- 4 + 3 + 1
The problem boils down to find the number of partition with distinct parts and simply subtract 1 from it. So I’ll focus on the core part.
Doing it by hand is easy. We choose the first element, e.g., 5, figure out
8-5=3, and try to split
3 into smaller parts. For human beings, checking “
3 is less than
5” on paper happens in an instant. But we need a way to tell the computer what is the current max, so it knows possible choices for the next number.
Visualize the result
Before we directly count the total number of sequences, it helps to visualize the result. Based on the idea from StackOverflow:
partition(n, maxi) into English: Parition the number
n into a decreasing sequence where the first element(largest one) is no bigger than
min(n-i, i-1) is to ensure the sequence is decreasing, and the max is no more than the number itself. To see that, let .
This also avoids extra calculations because the size for each part can’t be more than what we have. For example,
partition(5, 5) = partition(5, 14), so we don’t need to run the loop from 6 to 14.
Let’s count the total number
Base case is
0. When we have
count_p(0, i-1), it means
n=i or n=0, so the only possible partition is
n = n no matter what the max is.
It works, but it’s super inefficient. To see where recalculations happen, I modified the function as below:
If these results are stored somewhere, we can avoid all recalculations and just use it.
Let’s decipher the highlighted line:
p[i][j]: Partition the integer
i into a decreasing sequence with the first element(largest one) less than or equal to
j. Here we are accumulating the result. Say we want to partition 8. After selecting 5 as the first element, we want to find all decreasing sequences starting with 4 or less that sum to 8-5=3. As long as the first element is less than 5, the sequence is valid.
p[i][j-1] +: Accumulate the result as explained above.
p[i-j][min(i-j, j-1)]: Find all valid subsequences from
i-j(what’s left). This corresponds to our recursion
partitoin(n-i, min(n-i, i-1)).
Finally, we can find our result at
p[n][n]: partition the integer
n with the starting element less than or equal to
n. This is exactly what we’re looking for.
If you want to exclude
Here’s the table from
P(8). The result is at
p[8, 8] = 6 as we expected.