Signature Combo Builder
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.
Implement the function findSignatureCombos which identifies all unique combinations of dish prices that sum up to the targetPrice. You must satisfy the following conditions:
[2, 3] is considered the same as [3, 2]. The output should contain unique combinations only.targetPrice exactly should be included.function findSignatureCombos(dishPrices: number[], targetPrice: number): number[][]
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.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.dishPrices are positive integers.targetPrice is a positive integer.targetPrice, return an empty array [].dishPrices array might not be sorted; you may sort it if it helps your approach.Examples
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:
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:
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
1 <= dishPrices.length <= 301 <= dishPrices[i] <= 100 (Each dish price is between 1 and 100)1 <= targetPrice <= 500dishPrices and targetPrice are integers.[2,3] and [3,2] are the same combo).Loading editor...