Every cheapest way to order from a combo menu

A food ordering app wants to show a customer every cheapest way to buy the dishes they want.

The menu is a list of entries. Each entry is (id, price, items):

• id: a unique positive integer.
• price: a positive decimal string with at most two decimal places, such as "7.25".
• items: a comma-separated list of distinct item names, such as "burger" or "burger,shake,fries". An entry with more than one item is a combo.

The customer gives userWants, a list of distinct item names.

Implement cheapest_orders(menu, userWants) -> (min_total, combinations).

A combination is a set of entry IDs, each used at most once, whose items together include every name in userWants. Items the customer did not ask for may be included, and two entries may share an item.

• min_total is the lowest total price of any combination, as a string with two decimals. Use None if no combination exists.
• combinations lists every combination whose total equals min_total. Sort the IDs inside each combination, and sort the list of combinations. Return [] if none exists.
• An empty userWants costs "0.00" with one empty combination.

Constraints

• Up to 15 distinct wanted items.
• Up to 100 menu entries, each with up to 15 items.
• Compare prices exactly (do not let floating-point error decide ties).

Example 1

menu = [(1, "6.00", "taco"), (2, "5.00", "salad"), (3, "9.00", "taco,salad"),
        (4, "4.00", "soda"), (5, "13.00", "taco,salad,soda")]
userWants = ["taco", "salad", "soda"]

-> ("13.00", [[3, 4], [5]])

Buying 1, 2 and 4 costs 15.00. Entry 3 plus entry 4 and entry 5 alone both cost 13.00.

Example 2

menu = [(1, "2.00", "a"), (2, "2.00", "b"), (3, "4.00", "a,b"), (4, "4.00", "a,b,c")]
userWants = ["a", "b"]

-> ("4.00", [[1, 2], [3], [4]])

Entry 4 counts even though it includes c, which was not asked for.

Part I of this question usually asks only for the minimum total. Follow-ups may add item quantities, an exact-match rule, or a limit on how many combinations to return.

Reconstructed from the reported question; details may differ from what interviewers ask.