Distribute candies among children iii

Math Combinatorics

57.3% acceptance

Mar 31, 2026

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.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn distribute_candies(n: i32, limit: i32) -> i64 {
    let n = n as i64;
    let limit = limit as i64;
    fn c2(x: i64) -> i64 {
      if x < 2 { 0 } else { x * (x - 1) / 2 }
    }
    c2(n + 2) - 3 * c2(n - limit + 1) + 3 * c2(n - 2 * limit) - c2(n - 3 * limit - 1)
  }
}