Count Ways to Distribute Candies
MicrosoftThe problem
Given **n **distinct candies (numbered from 1 to n) and **k **bags. The task is to distribute all the candies among the bags such that each bag contains at least one candy.
There are multiple possible ways to organize the candies. Two arrangements are considered different if, in one arrangement, a group of candies in a specific bag is not entirely in the same bag in the other arrangement. The order of the bags and the sequence of candies within each bag do not affect the uniqueness of the arrangement.
For example, the distributions (1), (2,3) and (2), (1,3) are considered different because candies 2 and 3 that are together in (2,3) are separated into (2) and (1,3) in the other arrangement. However, (1), (2,3) and (1), (3,2) are treated as the same because the groups of candies remain the same.
Given two integers n and k, return the total number of distinct ways to distribute the candies. Since the answer can be large, return it modulo 109 + 7.
Input: n = 3, k = 2 Output: 3 Explanation: There are 3 ways to organize 3 candies into 2 bags: (1), (2,3) (2), (1,3) (3), (1,2)
Input: n = 5, k = 3 Output: 25 Explanation: You can distribute 5 candies into 3 bags in 25 ways, some of which include: (1), (2), (3,4,5) (1,2), (3), (4,5) (1,3), (2), (4,5) (1,4), (2,3), (5) (1,2,3), (4), (5)
Input: n = 6, k = 2
- 1 <= k <= n <= 1000
cpp
class Solution {
public:
int waysToDistribute(int n, int k) {
}
};java
class Solution {
public int waysToDistribute(int n, int k) {
}
}python
class Solution:
def waysToDistribute(self, n: int, k: int) -> int:javascript
class Solution {
waysToDistribute(n, k) {
}
}csharp
public class Solution {
public int waysToDistribute(int n, int k) {
}
}go
func waysToDistribute(n int, k int) int {
}Stuck? Show a way to structure it+
- 01Define `dp[i][j]` as partitions of i labeled candies into j nonempty unlabeled groups.
- 02Place candy i into one of j existing groups: `j * dp[i-1][j]`.
- 03Or let it start a new singleton group: `dp[i-1][j-1]`.
- 04Initialize `dp[0][0]=1` and compute modulo M.
Reference answer
Then expect these follow-ups
What changes if the bags are labeled?
Tests: combinatorics
How can you derive the recurrence combinatorially?
Tests: proof
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question