Solution

Method 1 – Inclusion-Exclusion Principle

Intuition

The problem asks for the number of ways to distribute n candies among 3 children, with each child getting at most limit candies. If there were no upper limit, the answer would be the number of non-negative integer solutions to a + b + c = n, which is C(n+3-1, 3-1) = C(n+2, 2). The limit constraint can be handled using the inclusion-exclusion principle: subtract cases where one or more children exceed the limit.

Approach

Count all non-negative solutions to a + b + c = n (no limits): use the stars and bars formula.
Subtract cases where at least one child gets more than limit candies:

For each subset of children, use inclusion-exclusion to add or subtract the number of ways where those children get at least limit+1 candies.

For each subset (represented by a bitmask of 3 bits), calculate the reduced candies after assigning at least limit+1 to selected children.
Sum up the contributions with the correct sign (add or subtract based on subset size).

Code

[{"language":"C++","code":"class Solution {\npublic:\n   int distributeCandies(int n, int limit) {\n      int ans = 0;\n      for (int mask = 0; mask < 8; ++mask) {\n        int cnt = 0, rem = n;\n        for (int i = 0; i < 3; ++i) {\n           if (mask & (1 << i)) {\n              rem -= (limit + 1);\n              cnt++;\n           }\n        }\n        if (rem < 0) continue;\n        int ways = (rem + 2) * (rem + 1) / 2;\n        ans += (cnt % 2 == 0 ? ways : -ways);\n      }\n      return ans;\n   }\n}

Related Tags