Count Distinct Subsets Under Capacity — Problem Statement & Solution Guide
Problem Description
Given an array of positive integers weights and a positive integer capacity, your task is to determine the total count of distinct non-empty subsets of weights such that the sum of elements in each subset is less than or equal to capacity. Each element from the input weights array can be used at most once in a single subset.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Count Distinct Subsets Under Capacity"
WHY DOES IT MATTER?
Meet‑in‑the‑middle is a cornerstone technique for tackling exponential‑time combinatorial problems where the input size is too large for full enumeration but small enough to split. It transforms an O(2^n) brute force into O(2^{n/2}) by exploiting the additive nature of subset sums, enabling solutions that fit within typical interview time limits.
OPTIMIZATION CHALLENGE
The key insight is that the sum of two independent subsets can be evaluated by pre‑computing all possible sums of each half and then using binary search (or two‑pointer technique) to count valid pairings in O(log 2^{n/2}) per element, collapsing the double loop into a logarithmic search.
REAL-WORLD CONNECTION
Think of a distributed load‑balancer that receives two streams of tasks. Each stream independently computes its total load; the coordinator then pairs loads from both streams to stay under a global capacity, similar to how the algorithm pairs subset sums from two halves.
During an interview, generate the subset sums first, sort only one list, and reuse the same binary‑search routine for every element of the other list. Avoid storing duplicate sums unless you need exact multiplicities; using a simple array of sums keeps the code concise and fast.
COMPLEXITY AT A GLANCE
O(2^{n/2} * log(2^{n/2}))O(2^{n/2})Core Theory — Why This Approach?
The problem asks for the number of distinct non‑empty subsets whose total weight does not exceed a given capacity. A naïve enumeration of all 2^n subsets quickly becomes infeasible when n exceeds 30 because the runtime grows exponentially and memory for storing intermediate results explodes. The optimal paradigm leverages the "meet‑in‑the‑middle" technique: split the array into two halves, enumerate all subset sums of each half (O(2^{n/2}) each), sort one list, and for each sum in the first list count how many sums in the second list keep the combined total ≤ capacity using binary search. This reduces the exponential factor from 2^n to roughly 2^{n/2}, making the algorithm tractable for n up to 40‑45. An alternative DP approach runs in O(n·capacity) time and O(capacity) space, which is optimal when capacity is small (≤10^5) but fails for large capacities due to memory constraints. The meet‑in‑the‑middle method therefore provides a balanced solution that works for both large n and large capacity values.
Interview Questions on This Problem
Q1How would you count subsets with sum ≤ C when n is up to 40 and weights can be as large as 10^9?
Use meet‑in‑the‑middle: split the array into two halves, generate all subset sums for each half, sort one list, and for each sum in the other list perform a binary search to find the number of complementary sums that keep the total ≤ C. Sum the counts, subtract 1 to exclude the empty subset.
Q2When would a classic DP knapsack counting approach be preferable over meet‑in‑the‑middle for this problem?
When the capacity C is relatively small (e.g., ≤10^5) and n can be large (up to 10^3‑10^4). In that regime O(n·C) time and O(C) space is feasible, while generating 2^{n/2} subset sums would be prohibitive.
Q3Explain how you would modify the solution to also return the actual subsets, not just the count, while keeping the algorithm efficient.
After counting, you can reconstruct subsets by storing for each half a map from sum to the list of bit‑masks that produce it (or a compressed representation). Then, for each valid pair of sums, combine the corresponding masks from both halves. This adds extra memory proportional to the number of stored subsets, but the enumeration remains O(2^{n/2}) and is only practical for moderate n.
Examples
Input
[1, 2, 3, 4, 5] and capacity 10
Output
31
Explanation: To solve this problem, we can use a bit mask approach. We iterate over all possible subsets of the input array and check if the sum of elements in the subset is less than or equal to the capacity. We use a bit mask to represent the presence or absence of each element in the subset. For each subset, we calculate the sum of its elements and check if it's less than or equal to the capacity. If it is, we increment the count of distinct subsets. Finally, we return the count of distinct subsets.
Input
[1, 2, 3] and capacity 4
Output
7
Explanation: We use the same bit mask approach as in the previous example. We iterate over all possible subsets of the input array and check if the sum of elements in the subset is less than or equal to the capacity. We calculate the sum of elements in each subset and check if it's less than or equal to the capacity. If it is, we increment the count of distinct subsets. Finally, we return the count of distinct subsets.
Constraints
- 1 <= weights.length <= 15
- 1 <= weights[i] <= 1000
- 1 <= capacity <= 15000
Optimal Approach & Strategy
Apply meet‑in‑the‑middle: split the array, list all subset sums of each half, sort one list, and for each sum in the other list use binary search to count compatible sums, achieving O(2^{n/2} log 2^{n/2}) time.
Brute Force Approach
Enumerate every subset, compute its sum, and increment a counter if the sum ≤ capacity. This runs in O(2^n) time and O(1) extra space.
Verified Code Solutions
function solution(weights, capacity) {
let n = weights.length;
let count = 0;
let max = (1 << n) - 1;
for (let mask = 0; mask <= max; mask++) {
let sum = 0;
for (let i = 0; i < n; i++) {
if ((mask & (1 << i)) !== 0) {
sum += weights[i];
}
}
if (sum <= capacity) {
count++;
}
}
return count;
}class Solution {
public:
int solution(vector<int>& weights, int capacity) {
int n = weights.size();
int count = 0;
int max = (1 << n) - 1;
for (int mask = 0; mask <= max; mask++) {
int sum = 0;
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) {
sum += weights[i];
}
}
if (sum <= capacity) {
count++;
}
}
return count;
}
};class Solution {
public int solution(int[] weights, int capacity) {
int n = weights.length;
int count = 0;
int max = (1 << n) - 1;
for (int mask = 0; mask <= max; mask++) {
int sum = 0;
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) {
sum += weights[i];
}
}
if (sum <= capacity) {
count++;
}
}
return count;
}
}def solution(weights, capacity):
n = len(weights)
count = 0
max = (1 << n) - 1
for mask in range(max + 1):
sum = 0
for i in range(n):
if (mask & (1 << i)) != 0:
sum += weights[i]
if sum <= capacity:
count += 1
return countfunction solution(weights, capacity) {
let n = weights.length;
let count = 0;
let max = (1 << n) - 1;
for (let mask = 0; mask <= max; mask++) {
let sum = 0;
for (let i = 0; i < n; i++) {
if ((mask & (1 << i)) !== 0) {
sum += weights[i];
}
}
if (sum <= capacity) {
count++;
}
}
return count;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.