Distribute Candies Among Children II solution and explanation
Google
9 more videos on this problem
Distribute Candies Among Children II | 4 Approaches | Detailed | Leetcode 2929 | codestorywithMIKcodestorywithMIK · 44:16 · 13K views
Distribute Candies Among Children II | Stars and Bars | Combinatorics | Leetcode 2929Techdose · 24:31 · 6K views
2929. Distribute Candies Among Children II | Leetcode Daily - PythonLeetcode Daily · 11:07 · 3K views
2929. Distribute Candies Among Children II | Min Max Range Distribution | BiWeekly 117Tech Courses · 12:55 · 1K views
Daily Leetcode #1888: Jun 01, 2025 - 2929. Distribute Candies Among Children IIProgramming Live with Larry · 16:32 · 1K views
🎥 Leetcode 2929 -Distribute Candies Among Children II | Complete Explanation + Code| Code With DeepaCode With Deepa · 9:04 · 758 views
Leetcode 2929. Distribute Candies Among Children II | 2929 Math + Inclusion-Exclusion ExplainedStatLearn Tech · 17:57 · 746 views
2929. Distribute Candies Among Children II (Leetcode Medium)Programming Live with Larry · 26:46 · 609 views
Distribute Candies Among Children II | LeetCode 2929 | Leetcode potd | Inclusion-Exclusion PrincipleCode Thoughts · 19:29 · 212 views
Distribute Candies Among Children II | LeetCode 2929 - Pythonimpoldev · 9:22 · 201 views
The problem
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 <= 106
Approach overview
Problem 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 1: Brute Force Using Nested Loops
This approach uses three nested loops to iterate over all possible distributions of candies to check each combination of candies for three children. This method directly checks if each combination satisfies the condition and counts the valid distributions.
def count_ways(n, limit):
count = 0
for i in range(limit + 1):
for j in range(limit + 1):
k = n - i - j
if 0 <= k <= limit:
count += 1
return count
n, limit = 5, 2
print(count_ways(n, limit))public class Main {
public static int countWays(int n, int limit) {
int count = 0;
for (int i = 0; i <= limit; i++) {
for (int j = 0; j <= limit; j++) {
int k = n - i - j;
if (k >= 0 && k <= limit) {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
int n = 5, limit = 2;
System.out.println(countWays(n, limit));
}
}#include <iostream>
using namespace std;
int countWays(int n, int limit) {
int count = 0;
for (int i = 0; i <= limit; i++) {
for (int j = 0; j <= limit; j++) {
int k = n - i - j;
if (k >= 0 && k <= limit) {
count++;
}
}
}
return count;
}
int main() {
int n = 5, limit = 2;
cout << countWays(n, limit) << endl;
return 0;
}function countWays(n, limit) {
let count = 0;
for (let i = 0; i <= limit; i++) {
for (let j = 0; j <= limit; j++) {
let k = n - i - j;
if (k >= 0 && k <= limit) {
count++;
}
}
}
return count;
}
const n = 5, limit = 2;
console.log(countWays(n, limit));#include <stdio.h>
int countWays(int n, int limit) {
int count = 0;
for (int i = 0; i <= limit; i++) {
for (int j = 0; j <= limit; j++) {
int k = n - i - j;
if (k >= 0 && k <= limit) {
count++;
}
}
}
return count;
}
int main() {
int n = 5, limit = 2;
printf("%d\n", countWays(n, limit));
return 0;
}using System;
class Program {
static int CountWays(int n, int limit) {
int count = 0;
for (int i = 0; i <= limit; i++) {
for (int j = 0; j <= limit; j++) {
int k = n - i - j;
if (k >= 0 && k <= limit) {
count++;
}
}
}
return count;
}
static void Main() {
int n = 5, limit = 2;
Console.WriteLine(CountWays(n, limit));
}
}In Python, the count_ways function similarly iterates through all feasible distributions of candies and counts those satisfying the constraints using nested loops.
Time Complexity: O(limit^2)
Space Complexity: O(1)
Approach 2: Dynamic Programming
Using dynamic programming, we can optimize the solution. We create a 3D DP array dp[i][j][k] where i, j, and k are the numbers of candies given to each child such that they collectively add up to n. Given constraints, we can fill the DP array by considering the subproblems of distributing fewer candies.
def count_ways(n, limit):
dp = [[0] * (limit + 1) for _ in range(limit + 1)]
total_ways = 0
for i in range(limit + 1):
for j in range(limit + 1):
k = n - i - j
if 0 <= k <= limit:
dp[i][j] = 1
total_ways += dp[i][j]
return total_ways
n, limit = 5, 2
print(count_ways(n, limit))public class Main {
public static int countWays(int n, int limit) {
int[][] dp = new int[limit + 1][limit + 1];
int totalWays = 0;
for (int i = 0; i <= limit; ++i) {
for (int j = 0; j <= limit; ++j) {
int k = n - i - j;
if (k >= 0 && k <= limit) {
dp[i][j] = 1;
totalWays += dp[i][j];
}
}
}
return totalWays;
}
public static void main(String[] args) {
int n = 5, limit = 2;
System.out.println(countWays(n, limit));
}
}#include <iostream>
#include <vector>
using namespace std;
int countWays(int n, int limit) {
vector<vector<int>> dp(limit + 1, vector<int>(limit + 1, 0));
for (int i = 0; i <= limit; i++) {
for (int j = 0; j <= limit; j++) {
int k = n - i - j;
if (k >= 0 && k <= limit) {
dp[i][j] = 1;
}
}
}
int total_ways = 0;
for (int i = 0; i <= limit; i++) {
for (int j = 0; j <= limit; j++) {
total_ways += dp[i][j];
}
}
return total_ways;
}
int main() {
int n = 5, limit = 2;
cout << countWays(n, limit) << endl;
return 0;
}function countWays(n, limit) {
let dp = Array.from({ length: limit + 1 }, () => Array(limit + 1).fill(0));
let totalWays = 0;
for (let i = 0; i <= limit; i++) {
for (let j = 0; j <= limit; j++) {
let k = n - i - j;
if (k >= 0 && k <= limit) {
dp[i][j] = 1;
totalWays += dp[i][j];
}
}
}
return totalWays;
}
const n = 5, limit = 2;
console.log(countWays(n, limit));#include <stdio.h>
#define MAX 1000000
int dp[MAX][3][3];
int countWays(int n, int limit) {
for (int i = 0; i <= limit; i++) {
for (int j = 0; j <= limit; j++) {
int k = n - i - j;
if (k >= 0 && k <= limit) {
dp[i][j][0] = 1;
}
}
}
int total_ways = 0;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
int k = n - i - j;
if (k >= 0) {
total_ways = (total_ways + dp[i][j][0]) % MAX;
}
}
}
return total_ways;
}
int main() {
int n = 5, limit = 2;
printf("%d\n", countWays(n, limit));
return 0;
}using System;
class Program {
static int CountWays(int n, int limit) {
int[,] dp = new int[limit + 1, limit + 1];
int totalWays = 0;
for (int i = 0; i <= limit; i++) {
for (int j = 0; j <= limit; j++) {
int k = n - i - j;
if (k >= 0 && k <= limit) {
dp[i, j] = 1;
totalWays += dp[i, j];
}
}
}
return totalWays;
}
static void Main() {
int n = 5, limit = 2;
Console.WriteLine(CountWays(n, limit));
}
}Python's count_ways function uses a similar tactic as C++ to precompute possible distributions within the limit using a 2D grid, summing valid solutions thereafter.
Time Complexity: O(limit^2)
Space Complexity: O(limit^2)
Approach 3: Combinatorial Mathematics + Principle of Inclusion-Exclusion
According to the problem description, we need to distribute n candies to 3 children, with each child receiving between [0, limit] candies.
This is equivalent to placing n balls into 3 boxes. Since the boxes can be empty, we can add 3 virtual balls, and then use the method of inserting partitions, i.e., there are a total of n + 3 balls, and we insert 2 partitions among the n + 3 - 1 positions, thus dividing the actual n balls into 3 groups, and allowing the boxes to be empty. Therefore, the initial number of schemes is C_{n + 2}^2.
We need to exclude the schemes where the number of balls in a box exceeds limit. Consider that there is a box where the number of balls exceeds limit, then the remaining balls (including virtual balls) have at most n + 3 - (limit + 1) = n - limit + 2, and the number of positions is n - limit + 1, so the number of schemes is C_{n - limit + 1}^2. Since there are 3 boxes, the number of such schemes is 3 times C_{n - limit + 1}^2. In this way, we will exclude too many schemes where the number of balls in two boxes exceeds limit at the same time, so we need to add the number of such schemes, i.e., 3 times C_{n - 2 times limit}^2.
The time complexity is O(1), and the space complexity is O(1).
function distributeCandies(n: number, limit: number): number {
const comb2 = (n: number) => (n * (n - 1)) / 2;
if (n > 3 * limit) {
return 0;
}
let ans = comb2(n + 2);
if (n > limit) {
ans -= 3 * comb2(n - limit + 1);
}
if (n - 2 >= 2 * limit) {
ans += 3 * comb2(n - 2 * limit);
}
return ans;
}func distributeCandies(n int, limit int) int64 {
comb2 := func(n int) int {
return n * (n - 1) / 2
}
if n > 3*limit {
return 0
}
ans := comb2(n + 2)
if n > limit {
ans -= 3 * comb2(n-limit+1)
}
if n-2 >= 2*limit {
ans += 3 * comb2(n-2*limit)
}
return int64(ans)
}impl Solution {
pub fn distribute_candies(n: i32, limit: i32) -> i64 {
if n > 3 * limit {
return 0;
}
let mut ans = Self::comb2(n + 2);
if n > limit {
ans -= 3 * Self::comb2(n - limit + 1);
}
if n - 2 >= 2 * limit {
ans += 3 * Self::comb2(n - 2 * limit);
}
ans
}
fn comb2(n: i32) -> i64 {
(n as i64) * (n as i64 - 1) / 2
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Using Nested Loops | Time Complexity: O(limit^2) |
| Dynamic Programming | Time Complexity: O(limit^2) |
| Combinatorial Mathematics + Principle of Inclusion-Exclusion | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Distribute Candies Among Children II easy or hard?
The problem is rated Medium on LeetCode. The brute force enumeration is straightforward, but recognizing the combinatorics structure or designing a scalable counting approach is what elevates the difficulty.
Distribute Candies Among Children II Python/Java solution
Typical implementations iterate over possible values for two children and compute the third value directly. Python, Java, C++, and similar languages can implement this in a few lines using nested loops and a validity check for the remaining candies.
How to solve Distribute Candies Among Children II in O(n)?
An even faster solution comes from combinatorics. First count all non‑negative solutions to a + b + c = n using combinations, then subtract cases where any child exceeds the limit using inclusion–exclusion. This converts the counting problem into a few constant‑time arithmetic operations, resulting in O(1) time.
What is the best approach for Distribute Candies Among Children II?
The most practical implementation approach is enumeration with constraints or dynamic programming counting. The brute force method fixes two variables and derives the third, giving O(limit^2) time and O(1) space. For more scalable variants, a DP counting approach with O(n × limit) time works well. Many advanced solutions also derive an O(1) combinatorics formula using inclusion–exclusion.
Is Distribute Candies Among Children II asked at Google/Amazon/Meta?
Problems involving constrained distributions and counting combinations appear frequently in interviews at companies like Google, Amazon, and Meta. Variants often test combinatorics reasoning, inclusion–exclusion, or dynamic programming for counting valid states.
What data structure is used in Distribute Candies Among Children II?
The brute force solution uses simple iteration with no additional data structures. The dynamic programming approach uses a one‑dimensional array where dp[i] stores the number of ways to form i candies after processing some children.
What is the time complexity of Distribute Candies Among Children II?
The straightforward nested loop enumeration runs in O(limit^2) time because two children are iterated explicitly while the third value is computed. A dynamic programming solution runs in O(n × limit) time by building ways to reach each candy sum. Space complexity is O(1) for brute force and O(n) for DP.