Count Ways to Distribute Candies

Count Ways to Distribute Candies

What is this problem about?

The Count Ways to Distribute Candies interview question asks you to find the number of ways to distribute $n$ unique candies into $k$ identical bags such that each bag contains at least one candy. This is a classic combinatorial problem involving the distribution of distinct objects into identical bins.

Why is this asked in interviews?

Google uses this Dynamic Programming interview pattern to see if a candidate can recognize and solve a problem that maps to "Stirling numbers of the second kind." It tests your ability to derive recurrence relations for distribution problems and optimize them using DP to avoid exponential time complexity.

Algorithmic pattern used

This problem is solved using 2D Dynamic Programming. Let dp[i][j] be the number of ways to distribute $i$ unique candies into $j$ identical bags.

• Base Cases: dp[i][i] = 1 (one candy per bag), and dp[i][1] = 1 (all candies in one bag).
• Transition: For the $i^{th}$ candy, you have two choices:
  1. Put it in a new, empty bag: This can be done in dp[i-1][j-1] ways.
  2. Put it in one of the $j$ bags already containing candies: This can be done in j * dp[i-1][j] ways.
• dp[i][j] = dp[i-1][j-1] + j * dp[i-1][j].

Example explanation

Distribute 3 unique candies (A, B, C) into 2 identical bags.

• Choice 1: Candy C goes into a new bag. (A, B) are in the first bag. Ways: {A, B}, {C}.
• Choice 2: Candy C goes into one of the 2 existing bags.
  • If we had 2 bags for (A, B), there's only one way: {A}, {B}.
  • Adding C to bag 1: {A, C}, {B}.
  • Adding C to bag 2: {A}, {B, C}. Total ways = 1 + 2 = 3.

Common mistakes candidates make

• Treating bags as distinct: If bags were distinct, you would multiply the result by $k!$.
• Ignoring the "at least one" rule: Failing to handle the requirement that no bag can be empty.
• Space Complexity: Using a full $n imes k$ matrix when only the previous row is needed for the current calculation.

Interview preparation tip

Practice identifying the difference between "labeled" and "unlabeled" objects/containers. This distinction changes the problem from simple powers or factorials to partitions and Stirling numbers.