Solution Explanation: Count Ways to Distribute Candies

This problem asks to find the number of ways to distribute n unique candies into k bags such that each bag contains at least one candy. The order of bags and candies within a bag doesn't matter.

The most efficient approach is using dynamic programming.

Dynamic Programming Approach

We define dp[i][j] as the number of ways to distribute i candies into j bags.

• Base Case: dp[0][0] = 1 (There's one way to distribute 0 candies into 0 bags: do nothing).

• Recursive Relation: To distribute i candies into j bags, we have two choices for the i-th candy:

  1. Place it in a new bag: This leaves i-1 candies to be distributed among j-1 bags. The number of ways to do this is dp[i-1][j-1].

  2. Place it in an existing bag: We already have j bags, and we can place the i-th candy in any of them. Therefore, we have j choices. The number of ways to do this is j * dp[i-1][j].

Therefore, the recursive relation is:

dp[i][j] = dp[i-1][j-1] + j * dp[i-1][j]

Code Implementation (Python):

class Solution:
    def waysToDistribute(self, n: int, k: int) -> int:
        mod = 10**9 + 7
        dp = [[0] * (k + 1) for _ in range(n + 1)]
        dp[0][0] = 1
        for i in range(1, n + 1):
            for j in range(1, min(i, k) + 1):  # j can't exceed i or k
                dp[i][j] = (dp[i - 1][j - 1] + j * dp[i - 1][j]) % mod
        return dp[n][k]
 

Time and Space Complexity Analysis:

• Time Complexity: O(n*k). The nested loops iterate through all possible combinations of candies and bags.

• Space Complexity: O(n*k). We use a 2D array dp to store the results of subproblems. This could be optimized to O(k) if we only need to keep track of the previous row in the DP table.

Other Languages: The logic remains the same across different programming languages; only the syntax changes. The provided solution includes implementations in Java, C++, Go, and TypeScript, showcasing this consistency. All these implementations achieve the same O(nk) time and O(nk) space complexity (or O(k) space with optimization).