A gift shop sells souvenirs with prices prices. A tourist with budget coins wants to know how many different bundles they could afford, where a bundle is any subset of the souvenirs (each item at most once) whose total price is at most budget. The empty bundle always counts. Write count_bundles(prices, budget) returning that number.
Examples
Input: prices = [3, 5, 8], budget = 8
Output: 5
Explanation: {}, {3}, {5}, {8} and {3, 5} cost at most 8; the other three subsets do not.
Input: prices = [10], budget = 4
Output: 1
Constraints
0 <= len(prices) <= 16,1 <= prices[i] <= 50,0 <= budget <= 800- Recursion depth is at most
len(prices) + 1.
Goals
- Enumerate subsets with an include/exclude recursion
- Count leaves instead of materialising every subset
- Memoise on (index, remaining budget) so repeated states are not recomputed