Frontend School

Signature Combo Builder

DSA
medium

Signature Combo Builder

Medium
Backtracking
Combinatorics
Arrays

Overview

At Zomato, we're always looking for innovative ways to enhance the customer experience. One exciting new feature we're developing is the 'Signature Combo Builder,' which allows customers to discover unique meal combinations from a restaurant's menu that perfectly match a specific target price. This not only encourages exploration but also helps restaurants curate special offers.

Your task is to implement the core logic for this feature: given a list of dish prices and a target price, find all unique combinations of dishes that sum up to exactly the target price. Each dish can be used multiple times in a combo.

What you need to do / Task

Implement the function findSignatureCombos which identifies all unique combinations of dish prices that sum up to the targetPrice. You must satisfy the following conditions:

  1. Combinations, not Permutations: The order of dishes within a combo does not matter. For example, [2, 3] is considered the same as [3, 2]. The output should contain unique combinations only.
  2. Reusable Dishes: Each dish (identified by its price) can be selected multiple times within a single combo.
  3. Exact Match: Only combinations that sum up to the targetPrice exactly should be included.

Input & output

Function Signature

function findSignatureCombos(dishPrices: number[], targetPrice: number): number[][]

Parameters

  • dishPrices: An array of positive integers representing the prices of available dishes on a menu. These prices are unique numeric values, but can be used multiple times.
  • targetPrice: A positive integer representing the exact total price that the combo must achieve.

Return Value

  • A number[][] (an array of arrays of numbers), where each inner array represents a unique combination of dish prices that sums up to targetPrice. The order of combinations in the outer array, and the order of prices within each inner array, does not matter for uniqueness, but it is recommended to sort the prices within each combination for consistent output and easier uniqueness checking.

Clarifications

  • All dishPrices are positive integers.
  • targetPrice is a positive integer.
  • If no combinations can be found that sum up to targetPrice, return an empty array [].
  • The input dishPrices array might not be sorted; you may sort it if it helps your approach.

Examples

1

Example 1

Input:

dishPrices = [2, 3, 6, 7], targetPrice = 7

Output:

[[7], [2, 2, 3]]

Note:

From the dishes [2, 3, 6, 7] and target 7, two unique combos are possible:

  1. [7] (using the dish with price 7 once)
  2. [2, 2, 3] (using the dish with price 2 twice, and the dish with price 3 once)
2

Example 2

Input:

dishPrices = [2, 3, 5], targetPrice = 8

Output:

[[2, 2, 2, 2], [2, 3, 3], [3, 5]]

Note:

From the dishes [2, 3, 5] and target 8, three unique combos are possible:

  1. [2, 2, 2, 2]
  2. [2, 3, 3]
  3. [3, 5]
3

Example 3

Input:

dishPrices = [4, 6], targetPrice = 3

Output:

[]

Note:

No combination of dishes with prices 4 and 6 can sum up to exactly 3.

Constraints

Constraints & assumptions

  • 1 <= dishPrices.length <= 30
  • 1 <= dishPrices[i] <= 100 (Each dish price is between 1 and 100)
  • 1 <= targetPrice <= 500
  • All dishPrices and targetPrice are integers.

What interviewers evaluate

  • Algorithmic Correctness: The solution must correctly identify all unique combinations that sum to the target price, adhering to the reusability of dishes.
  • Efficiency: The solution should demonstrate an understanding of time and space complexity, and avoid unnecessary computations or storage.
  • Uniqueness Handling: Proper handling of duplicate combinations in the output is crucial (e.g., [2,3] and [3,2] are the same combo).
  • Code Quality: Readability, maintainability, and adherence to standard coding practices.

Loading editor...