Menu Combination Sum
Updated
Problem statement
A restaurant menu lists the price of each item in prices. Prices are whole numbers, and no two items cost the same. You want to spend exactly target.
Return every different order whose prices add up to exactly target. You may order the same item any number of times. Two orders are the same if they have the same items the same number of times, so list each order only once.
Write each order as a list of its prices in increasing order (repeated prices next to each other). Sort the orders by comparing their first prices, then their second prices, and so on. If no order works, return an empty list.
Function
combinationSum(prices: int[], target: int) → List<List<Integer>>Examples
Example 1
prices = [3,5,8]target = 11return = [[3,3,5],[3,8]]Two orders cost exactly 11: 3 + 3 + 5 and 3 + 8. Ordering 5 + 3 + 3 is the same order as 3 + 3 + 5, so it is listed once. [3,3,5] comes first because its second price, 3, is smaller than 8.
Example 2
prices = [4,2,7]target = 8return = [[2,2,2,2],[2,2,4],[4,4]]The 2 item can be ordered four times, or twice with the 4 item, and the 4 item can be ordered twice. The 7 item leaves 1, which no item costs. So there are three orders.
Example 3
prices = [5,10]target = 3return = []Every item costs more than 3, so no order works.
Constraints
1 <= prices.length <= 302 <= prices[i] <= 40- All values in
pricesare different. 1 <= target <= 40- The input has fewer than
150different orders that add up totarget.
More Airbnb Phone Screen questions
- Read Across Sound TracksPHONE SCREEN · Seen Nov 2026
- Text JustificationPHONE SCREEN · Seen Nov 2026
- Decode and Store StringsPHONE SCREEN · Seen Oct 2026
- Print Sentences as TablePHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
- Detonate Bombs with Chain ReactionsPHONE SCREEN · Seen Aug 2026
- Smallest Common RegionPHONE SCREEN · Seen Aug 2026
- Longest Chain BookingPHONE SCREEN · Seen Aug 2026
- Nested List Iterator with RemovePHONE SCREEN · Seen Jul 2026
- Parse Query StringPHONE SCREEN · Seen May 2026
- Pacific Atlantic Water FlowPHONE SCREEN · Seen May 2023
Similar questions at other companies
- Largest Number Below N from Reusable DigitsByteDance · PHONE SCREENByteDance interview questions
- SubsetsTemu · PHONE SCREENTemu interview questions
- PermutationsEPAM · PHONE SCREENEPAM interview questions
- Expand Attribute CombinationsPinterest · PHONE SCREENPinterest interview questions
- All Subsets with a Given SumApple · PHONE SCREENApple interview questions
- Combination Sum with Unlimited ReuseIMC Trading · PHONE SCREENIMC Trading interview questions
- SubsetsBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Validate a Mahjong Hand PartitionDuolingo · PHONE SCREENDuolingo interview questions
- Winning Draws for a Mahjong HandZip · PHONE SCREENZip interview questions
- Count Plus and Minus Sign PatternsAdobe · PHONE SCREENAdobe interview questions
Interview reports that mention this question
Airbnb interview experiences
- Airbnb SWE OA: Four-Level Banking System: 1 Experience
- Airbnb Campus and Full-Time SWE OA / Interviews: 9 Experiences
- Airbnb Intern OA and Phone Screens: 17 Experiences (Part 6 of 7)
- Airbnb Intern OA and Onsite Rounds: 16 Experiences (Part 5 of 7)
- Airbnb Intern OA, Diplomacy Game: 19 Experiences (Part 4 of 7)