Cheapest Menu Combinations

Step 1: Clarify

You must cover every distinct item in `userWants`. Menu entries can over-deliver items. Among all covering subsets of the menu, keep only those with the smallest summed price, then return their ID sets in a canonical sorted form.

Ask: Are IDs always unique? Can the same item appear on many dishes? Is `userWants` a multiset or a set? (Here: set of required items.)

Step 2: Trace the example

Required: sandwich, pasta, coke.

Useful dishes (those that contribute at least one required item):

| ID | Price | Covers | |----|-------|--------| | 2 | 8 | sandwich, coke | | 3 | 4 | pasta | | 4 | 2 | coke | | 5 | 6 | pasta, coke | | 6 | 8 | coke | | 7 | 5 | sandwich |

Min-cost covers at 11: `{3,4,7}` and `{5,7}`. Dish 1 (pizza only) never helps.

Step 3: Brute force

Enumerate all `2^n` subsets of menu entries (`n <= 15`). For each subset, compute the union of items and total cost. Track the minimum cost and collect matching ID lists. Sort for the required output order.

Step 4: Speed up with bitmasks

Map each distinct wanted item to a bit. Convert every dish to `(id, price, mask)`. A subset is valid when OR of masks equals the full mask. Comparing costs with money: use floats carefully or work in integer cents.

Optional DP: `dp[mask] = min cost to achieve coverage mask`, plus store predecessor/lists of ways — useful when you only need one answer, heavier when you need all min-cost combinations.

Step 5: Implement carefully

• Skip dishes whose mask is 0 (no overlap with `userWants`).
• Deduplicate combinations (same ID set found once).
• Sort each ID list, then sort the list of lists.
• Impossible → `[]`.

Step 6: Complexity

• Time: `O(2^n * n)` for subset enumeration with `n = menu.length` (after filtering irrelevant dishes).
• Space: `O(n + number of answers)`.

Step 7: Follow-ups

For larger `n`, use meet-in-the-middle, branch-and-bound on cost, or integer-linear / set-cover heuristics. For quantities, expand bits or use a count vector instead of a bitmask.