Lv.3binary-searchmeet-in-the-middlesortingtwo-pointers
Subsets Within a Weight Limit
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
There are N items; item i weighs weights[i]. Count the subsets of items whose total weight is at most limit.
The empty subset counts, and different items are distinguished even if their weights are equal.
Examples
| weights | limit | result |
|---|---|---|
[1, 2, 3] | 3 | 5 |
[5, 5] | 4 | 1 |
[2, 2, 2] | 100 | 8 |
Example 1 — {}, {1}, {2}, {3}, {1, 2}.
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(weights: int[], limit: long) → long
Constraints
-
weights.length,weights[i] -
limit - The answer is at most and fits in 64 bits.
Expected complexity
- Time
- O(2^(N/2) * N)
- Space
- O(2^(N/2))
Examples
| weights | limit | Expected |
|---|---|---|
[1,2,3] | 3 | 5 |
[5,5] | 4 | 1 |
[2,2,2] | 100 | 8 |
Hint
Hint
Split the items into two halves and list every subset sum of each half ( each). Each choice is a pair of half
choices, so for every sum a of the first half add the number of second-half sums ≤ limit - a — binary search in the
sorted second list, or a two-pointer sweep over both sorted lists. Enumerating all subsets exceeds the time limit.
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 | 11 | verdict only |
| performance | 60 | 4 | verdict only |