Watch 10 video solutions for Distribute Candies Among Children II, a medium level problem involving Math, Combinatorics, Enumeration. This walkthrough by codestorywithMIK has 13,554 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given two positive integers n and limit.
Return the total number of ways to distribute n candies among 3 children such that no child gets more than limit candies.
Example 1:
Input: n = 5, limit = 2 Output: 3 Explanation: There are 3 ways to distribute 5 candies such that no child gets more than 2 candies: (1, 2, 2), (2, 1, 2) and (2, 2, 1).
Example 2:
Input: n = 3, limit = 3 Output: 10 Explanation: There are 10 ways to distribute 3 candies such that no child gets more than 3 candies: (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) and (3, 0, 0).
Constraints:
1 <= n <= 1061 <= limit <= 106Problem Overview: You are given n candies and three children. Each child can receive between 0 and limit candies. The task is to count how many distributions (a, b, c) satisfy a + b + c = n while keeping every value ≤ limit. This turns into a counting problem over constrained integer triples, which falls under math and combinatorics.
Approach 1: Brute Force Using Nested Loops (Time: O(limit2), Space: O(1))
Enumerate all possible values for the first two children. Use two nested loops where a ranges from 0 to limit and b ranges from 0 to limit. For each pair, compute c = n - a - b. If 0 ≤ c ≤ limit, the distribution is valid and you increment the count. This works because once two values are fixed, the third is uniquely determined by the sum constraint. The method is simple and easy to reason about, making it a good baseline when first approaching enumeration problems.
Approach 2: Dynamic Programming Counting (Time: O(n × limit), Space: O(n))
Dynamic programming treats the problem as distributing candies child by child. Define dp[i] as the number of ways to distribute exactly i candies among the processed children. Start with dp[0] = 1. For each child, build a new DP array where you try giving that child 0..limit candies and accumulate the number of ways to reach each sum. The transition is new_dp[s + k] += dp[s] for every valid k from 0 to limit. After processing all three children, the answer is dp[n]. This converts the triple enumeration into structured state transitions and avoids explicitly checking every pair combination.
The DP formulation generalizes well. If the number of children increases or limits vary per child, the same idea still works with minimal changes. It also illustrates how counting problems with constraints can be modeled with dynamic programming instead of direct iteration.
Recommended for interviews: Start with the nested loop enumeration. It shows you understand the constraint a + b + c = n and how fixing two variables determines the third. Then discuss the DP counting formulation as the scalable approach. Strong candidates often also mention the combinatorics insight: the problem can be solved with inclusion–exclusion in O(1) time using counting formulas.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Using Nested Loops | O(limit²) | O(1) | Best for understanding the constraint a + b + c = n and when limits are small. |
| Dynamic Programming Counting | O(n × limit) | O(n) | Preferred when the number of children or constraints increase and brute force enumeration becomes harder to manage. |