Balls and Bins
Problem Statement
Givenm balls and n bin, find out how many ways exist to assign the balls to then bins. Note: the buckets have no order. That is,
(1,2,3) and (3,2,1) are considered the same.
Example
Input: m = 3, n = 2
Output: 2
Explanation: (1,2) and (3,0)Solution
This can be solved using dynamic programming. The solution builds up upon the solution of its smaller subproblems. Assumingm = 3, n = 2 this means that number of ways 3 balls can be distributed to 2 bins is the same as the number of ways 3 balls can be distributed to 1 bin plus the number of ways if alle (2) bins each of the n bins had a ball and we need to distribute the remaining m - n balls on the n bins.
int assignBalls(int m, int n) {
if (m == 0 || n == 1) {
return 1;
}
if (n > m) {
return assignBalls(m, m);
} else {
return assignBalls(m, n - 1) + assignBalls(m - n, n);
}
}