Restaurant Menu Combinations
Asked at Airbnb· Screen
Reported by the problem's creator, not verified
A guest wants to order dishes whose prices add up to exactly a given amount. The menu lists each dish as [name, price] with prices in whole cents (so $2.15 is 215). Names are unique, and the list order is the menu order. An order is any non-empty collection of dishes where each dish may be ordered any number of times, and the sequence does not matter.
Examples
Example 1
Input:
{"menu":[["Fruit",215],["Fries",275],["Salad",335],["Wings",355],["Mozzarella",420],["Plate",580]],"target":550}Output:
[["Fruit","Salad"],["Fries","Fries"]]Explanation: Two Fries cost 275 + 275 = 550 and Fruit + Salad cost 215 + 335 = 550. Orders list dishes in menu order and are sorted by menu position, so ["Fruit", "Salad"] (positions 0, 2) comes before ["Fries", "Fries"] (positions 1, 1).