1769. Subsets Under Budget
A gift shop lists the prices of n small souvenirs in the array prices. A visitor wants to buy a non-empty bundle of different items (each item at most once) and can spend at most budget in total. Two bundles are different when they contain a different set of positions, even if the prices happen to be equal.
Return the number of non-empty subsets of prices whose total is less than or equal to budget, as an int. Because the array is tiny, enumerate every bitmask from 1 to 2^n - 1, add up the prices selected by its set bits, and count the masks that fit. Sums can reach 1.5 * 10^7, so keep them in a wide enough integer type. The running time is O(2^n * n) with O(1) extra space.
Example 1
- Input:
- prices = [3,5,7], budget = 10
- Output:
- 5
- Explanation:
Affordable bundles are {3}, {5}, {7}, {3,5} and {3,7}, so the answer is 5.
Example 2
- Input:
- prices = [4,4,4], budget = 3
- Output:
- 0
- Explanation:
Every single item costs more than the budget, so nothing is affordable.
Example 3
- Input:
- prices = [1,2,3,4], budget = 6
- Output:
- 10
- Explanation:
Counting by masks gives 10 affordable non-empty bundles out of 15.
Constraints
1 ≤ n ≤ 15; 1 ≤ prices[i] ≤ 106; 1 ≤ budget ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 4,000 msC++ 1,000 msJava 2,000 msJavaScript 2,000 msTypeScript 2,000 ms
Expected complexity
- Time
- O(2^n * n)
- Space
- O(1)