Split Candy Bags Equally
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
Two brothers received bags of candy; bag i holds nums[i] candies and bags cannot be opened.
Return true if all bags can be handed out so that both brothers get exactly the same number of candies, otherwise false.
Examples
| nums | result |
|---|---|
[1, 5, 11, 5] | true |
[1, 2, 3, 5] | false |
[3, 3, 3, 4, 5] | true |
Example 1 — [11] and [1, 5, 5] both hold 11 candies.
Example 2 — There are 11 candies in total, which cannot be split evenly.
Example 3 — [3, 3, 3] and [4, 5] both hold 9 candies.
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(nums: int[]) → bool
Constraints
-
nums.length -
nums[i]
Expected complexity
- Time
- O(N * S)
- Space
- O(S)
Examples
| nums | Expected |
|---|---|
[1,5,11,5] | true |
[1,2,3,5] | false |
[3,3,3,4,5] | true |
Hint
Hint
If the total is odd the answer is false; otherwise ask whether some subset sums to exactly . Trying every subset is
. Keep can[s] ("sum s is reachable") and, for each bag x, update can[s] |= can[s - x] with s going downwards
so a bag is used at most once: . A bitset (can |= can << x) processes many sums per machine word.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1000 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1400 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 13 | verdict only |
| performance | 60 | 4 | verdict only |