Candies Into Bags

Hard

There are candies distinct candies (each has its own number) and bags identical bags. Put all the candies into the bags so that no bag is left empty. The bags are indistinguishable and the order of candies inside a bag does not matter: two arrangements are the same when they group the candies the same way. For example, {1}, {2, 3} and {3, 2}, {1} are the same, while {1}, {2, 3} and {2}, {1, 3} are different. Return the number of different arrangements modulo 10⁹ + 7.

Example 1

candies=3, bags=3 → 1

Every bag gets exactly one candy, so there is a single way.

Example 2

candies=4, bags=3 → 6

Two of the candies share a bag and the other two are alone. The pair can be chosen in 6 ways.

Example 3

candies=5, bags=2 → 15

Constraints

1 ≤ bags ≤ candies ≤ 1000

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Dynamic Programming

Similar problems

Pattern With Dot and Star Hard Longest Balanced Bracket Stretch Hard Water Between Walls Hard Does the Text Fit the Pattern Hard Biggest Solid Panel Block Hard

Input

candies=3, bags=3

Expected

Run checks the first 3 tests in your browser. Submit checks all 81 tests on the server, hidden ones included.