Count Integer Partitions
Problem
A partition of n is a way to write n as a sum of positive whole numbers where the order does not matter (3 + 1 and 1 + 3 are the same). Print the number of partitions of n. For 4: 4, 3+1, 2+2, 2+1+1, 1+1+1+1 gives 5.
Constraints
- 1 <= n <= 40
Examples
Input
4
Output
5
Solutions
This is the same as counting coins of values 1..n. The order of loops (part first, then sum) makes sure that 3+1 and 1+3 are not both counted. O(n^2) time.
/*
* Problem : Count partitions.
* Input : One number n.
* Output : Number of partitions.
* Approach: Dynamic programming.
* Time : O(n^2)
* Space : O(n)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
// This method solves the task. It receives the input and returns the answer.
static long solve(long n) {
// Step 1: ways[s] counts the ways to make the sum s. There is one way to make 0: use nothing.
int total = (int) n;
long[] ways = new long[total + 1];
ways[0] = 1;
// Step 2: Allow the parts one size at a time (1, then 2, ...). Using sizes in order means each partition is counted once.
for (int part = 1; part <= total; part++) {
for (int sum = part; sum <= total; sum++) {
ways[sum] += ways[sum - part];
}
}
return ways[total];
}
public static void main(String[] args) {
long n = new Scanner(System.in).nextLong();
System.out.println(solve(n));
}
}
Hints (2)
- Why is there one way to make 0?
- What happens if the loops are swapped?