What is the best approach for solving the Distribute Candies Among Children I problem?

The brute-force approach is easy to implement but may not be efficient. A more optimal approach involves using combinatorics or dynamic programming to count valid distributions without unnecessary computations.

How do I handle the constraint of no child receiving more than the limit?

Ensure that the distribution checks never exceed the limit value for any child. This can be done in the brute-force solution by filtering out invalid distributions during iteration or through careful combinatorial counting.

What is the time complexity of the brute-force solution?

The brute-force solution has a time complexity of O(limit^3) because we are checking all possible distributions of candies using nested loops.

How can I optimize the solution to the Distribute Candies Among Children I problem?

You can optimize the solution by using combinatorics to calculate the number of valid distributions without generating each possible combination or by employing dynamic programming to avoid redundant calculations.

Does this problem have any edge cases I should be aware of?

Yes, edge cases include when n is very small compared to the limit, or when n is very large, testing the algorithm's ability to handle the upper bounds of the problem constraints.

#2928

Easy

auto_awesome数学·结合·combinatorics

LeetCode 题解工作台

给小朋友们分糖果 I

给你两个正整数 n 和 limit 。请你将 n 颗糖果分给 3 位小朋友，确保没有任何小朋友得到超过 limit 颗糖果，请你返回满足此条件下的总方案数。示例 1：输入： n = 5, limit = 2 输出： 3 解释：总共有 3 种方法分配 5 颗糖果，且每位小朋友的糖果数不超过…

数学组合数学枚举

题目描述

给你两个正整数 n 和 limit 。

请你将 n 颗糖果分给 3 位小朋友，确保没有任何小朋友得到超过 limit 颗糖果，请你返回满足此条件下的 总方案数 。

示例 1：

输入：n = 5, limit = 2
输出：3
解释：总共有 3 种方法分配 5 颗糖果，且每位小朋友的糖果数不超过 2 ：(1, 2, 2) ，(2, 1, 2) 和 (2, 2, 1) 。

示例 2：

输入：n = 3, limit = 3
输出：10
解释：总共有 10 种方法分配 3 颗糖果，且每位小朋友的糖果数不超过 3 ：(0, 0, 3) ，(0, 1, 2) ，(0, 2, 1) ，(0, 3, 0) ，(1, 0, 2) ，(1, 1, 1) ，(1, 2, 0) ，(2, 0, 1) ，(2, 1, 0) 和 (3, 0, 0) 。

提示：

1 <= n <= 50
1 <= limit <= 50

lightbulb

解题思路

方法一：组合数学 + 容斥原理

根据题目描述，我们需要将 $n$ 个糖果分给 $3$ 个小孩，每个小孩分到的糖果数在 $[0, limit]$ 之间。

这实际上等价于把 $n$ 个球放入 $3$ 个盒子中。由于盒子可以为空，我们可以再增加 $3$ 个虚拟球，然后再利用隔板法，即一共有 $n + 3$ 个球，我们在其中 $n + 3 - 1$ 个位置插入 $2$ 个隔板，从而将实际的 $n$ 个球分成 $3$ 组，并且允许盒子为空，因此初始方案数为 $C_{n + 2}^2$ 。

我们需要在这些方案中，排除掉存在盒子分到的小球数超过 $limit$ 的方案。考虑其中有一个盒子分到的小球数超过 $limit$ ，那么剩下的球（包括虚拟球）最多有 $n + 3 - (limit + 1) = n - limit + 2$ 个，位置数为 $n - limit + 1$ ，因此方案数为 $C_{n - limit + 1}^2$ 。由于存在 $3$ 个盒子，因此这样的方案数为 $3 \times C_{n - limit + 1}^2$ 。这样子算，我们会多排除掉同时存在两个盒子分到的小球数超过 $limit$ 的方案，因此我们需要再加上这样的方案数，即 $3 \times C_{n - 2 \times limit}^2$ 。

时间复杂度 $O(1)$ ，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def distributeCandies(self, n: int, limit: int) -> int:
        if n > 3 * limit:
            return 0
        ans = comb(n + 2, 2)
        if n > limit:
            ans -= 3 * comb(n - limit + 1, 2)
        if n - 2 >= 2 * limit:
            ans += 3 * comb(n - 2 * limit, 2)
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate suggests an efficient combinatorial approach.
question_mark
Candidate considers dynamic programming for optimization.
question_mark
Candidate does not consider the brute-force method but instead tries an optimized solution.

warning

常见陷阱

外企场景

error
Forgetting to check that the sum of candies matches n.
error
Incorrectly counting distributions where children receive more than the limit.
error
Overcomplicating the problem with unnecessary optimizations before checking the brute-force solution.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Varying the number of children to test scalability.
arrow_right_alt
Adjusting the limit per child to explore edge cases.
arrow_right_alt
Considering the possibility of using more advanced combinatorics techniques to optimize the solution.

help

常见问题

外企场景

继续练习

#2929 给小朋友们分糖果 II #3272 统计好整数的数目 #3470 全排列 IV