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);
}
}