FastPrepMenu Combination Sum

Menu Combination Sum

Airbnb logoAirbnb● MediumINTERNPHONE SCREEN

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 <= 30
  • 2 <= prices[i] <= 40
  • All values in prices are different.
  • 1 <= target <= 40
  • The input has fewer than 150 different orders that add up to target.

More Airbnb Phone Screen questions

Similar questions at other companies

Interview reports that mention this question

Airbnb interview experiences

All Airbnb interview questionsSee Airbnb hiring insights
Saved
class Solution {
    public List<List<Integer>> combinationSum(int[] prices, int target) {
      // Write your code here.
    }
}
Checking account…