Funcia
Lv.3binary-searchmeet-in-the-middlesortingtwo-pointers

Subsets Within a Weight Limit

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
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

weightslimitresult
[1, 2, 3]35
[5, 5]41
[2, 2, 2]1008

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

  • 1≤N=1 \le N = weights.length ≤40\le 40, 1≤1 \le weights[i] ≤109\le 10^9
  • 0≤0 \le limit ≤4×1010\le 4 \times 10^{10}
  • The answer is at most 2402^{40} and fits in 64 bits.

Expected complexity

Time
O(2^(N/2) * N)
Space
O(2^(N/2))

Examples

weightslimitExpected
[1,2,3]35
[5,5]41
[2,2,2]1008

Hint

Hint

Split the items into two halves and list every subset sum of each half (2202^{20} 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 2N2^N subsets exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251000 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4011verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.