Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Balls and Bins

Sharing is caring!

Problem Statement
Given m 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. Assuming m = 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);
        }
}