Given item prices and a budget, return how many subsets of items have a total cost
within the budget (cost <= budget). The empty subset (cost 0) counts.
groceryBudget(prices, budget)
Input format: prices | budget.
prices=[2, 3], budget=4 // → 3 ({}, {2}, {3})
prices=[1, 1], budget=2 // → 4 (all subsets fit)
prices=[5], budget=2 // → 1 (only {})
Counting subsets satisfying a condition suggests the same include/exclude tree used to enumerate all subsets — except here you don't materialize every subset, only count how many stay within budget.
For each item, two choices: include it (add its price to the running total) or exclude it (unchanged). Every subset corresponds to exactly one sequence of include/exclude decisions, and vice versa. Exploring both branches at every item visits all 2ⁿ subsets exactly once.
Once every item has a decision, the subset and its cost are fixed. Check: is it within budget? If so, count it. Summing include and exclude branches at every level tallies how many leaves satisfy the budget.
Each call asks a smaller version of the same question: given the undecided items and the amount spent so far, how many ways to finish within budget? Recursing on the rest peels off one item and asks the identical question with one fewer item and a possibly higher total.
Once spending exceeds budget, continuing to add items (all positive prices) can only get worse — no such subset can recover. Pruning that branch early (returning 0 immediately) is a valid optimization that saves work without changing the answer. Without it, the algorithm still gets the correct result, just by walking further before confirming invalidity — exhaustiveness guarantees correctness either way; pruning only affects how much of the tree gets visited.
"Within budget" depends on which specific items were chosen, not just how many — no closed-form shortcut exists. The include/exclude tree is the natural way to check the budget condition against every possible selection.
def grocery_budget(prices, budget):
def count(i, spent):
if spent > budget:
return 0
if i == len(prices):
return 1
# exclude prices[i], or include it
return count(i + 1, spent) + count(i + 1, spent + prices[i])
return count(0, 0)
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.