Shopping Options Budget
MediumCombinatorics · Amazon
You want to buy exactly one item from each of four categories (say jeans, shoes, skirts and tops). The available prices are given in four lists a, b, c and d, one per category. Two entries at different positions of a list are different items, even if they have the same price.
Return the number of different ways to choose one item from each list such that the total price is at most budget. If any list is empty, the answer is 0.
Example 1
- Input:
- a = [1, 4], b = [2, 3], c = [5], d = [1, 2, 6], budget = 11
- Output:
- 4
- Explanation
- There are 2 * 2 * 1 * 3 = 12 combinations. Any combination with the 6 from
dcosts at least 1 + 2 + 5 + 6 = 14, too much. Of the other 8, the ones that fit are 1+2+5+1, 1+2+5+2, 1+3+5+1 and 1+3+5+2; every combination with the 4 fromacosts at least 12. That gives 4.
Example 2
- Input:
- a = [2, 2], b = [1], c = [1], d = [1], budget = 5
- Output:
- 2
- Explanation
- Both 2s in
aare separate items, and each makes a total of exactly 5, which is allowed, so there are 2 ways.
Constraints
0 <= a.length, b.length, c.length, d.length <= 10001 <= price <= 10^61 <= budget <= 4 * 10^6