What is the most efficient way to solve the Distribute Candies Among Children II problem?

The most efficient way is to apply combinatorics to enumerate valid candy distributions while keeping track of the limit for each child, optimizing the process to avoid brute force.

How do I ensure that no child gets more than the limit number of candies?

The solution involves calculating the number of valid combinations where each child receives no more than the specified limit, using combinatorics and constraints to prune invalid combinations.

Can this problem be solved using brute force?

While brute force is possible, it is inefficient for large inputs. Optimizing the solution using combinatorics and dynamic programming is the recommended approach.

What mathematical concept should I focus on for this problem?

The problem primarily involves combinatorics and enumeration, where you need to count the valid distributions of candies under constraints.

How can I handle large inputs efficiently in this problem?

By using combinatorial counting methods and dynamic programming techniques, you can compute the result efficiently without the need for brute force enumeration.

#2929

Medium

auto_awesome数学·结合·combinatorics

LeetCode 题解工作台

给小朋友们分糖果 II

给你两个正整数 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 <= 10⁶
1 <= limit <= 10⁶

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

复杂度分析

指标	值
时间	O(1)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Strong understanding of combinatorics and enumeration techniques.
question_mark
Ability to optimize a brute-force solution for large input sizes.
question_mark
Familiarity with problem-solving patterns involving distribution under constraints.

warning

常见陷阱

外企场景

error
Forgetting to account for the limit on the number of candies each child can receive.
error
Incorrectly assuming the problem can be solved through brute-force enumeration without optimization.
error
Misunderstanding the problem's constraints, leading to an inefficient or incorrect solution.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Distribute candies among a different number of children.
arrow_right_alt
Distribute candies with varying limits per child.
arrow_right_alt
Find the number of ways to distribute candies when each child must receive at least one candy.

help

常见问题

外企场景

继续练习

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