Curated Product Bundles
Nykaa aims to enhance customer experience by offering personalized, curated product bundles. To achieve this, we need a system that can efficiently identify all potential product combinations that meet specific criteria. This problem challenges you to develop an algorithm that generates valid product bundles based on a given budget and a minimum requirement for distinct product categories.
You are tasked with implementing a function findCuratedBundles that takes a list of available products, a maximum budget, and a minDistinctCategories count. Your function should return all unique combinations of products (represented by their IDs) that satisfy the following conditions:
budget.minDistinctCategories unique product categories.[["A", "B"], ["A", "C"]] is sorted before [["A", "D"]]).products: An array of objects, where each object represents a product.
interface Product {
id: string; // Unique identifier for the product
category: string; // Category of the product (e.g., "Skincare", "Makeup")
price: number; // Price of the product
}
budget: A number representing the maximum allowed total price for a bundle.minDistinctCategories: A number representing the minimum required count of unique categories within a bundle.string[][]). Each inner array represents a valid product bundle and contains the ids of the products in that bundle, sorted lexicographically. The outer array (list of bundles) should also be sorted lexicographically.products array can be chosen at most once for a single bundle.Examples
Example 1
Input:
products = [ { id: "P1", category: "Skincare", price: 100 }, { id: "P2", category: "Makeup", price: 200 }, { id: "P3", category: "Skincare", price: 150 }, { id: "P4", category: "Haircare", price: 50 } ], budget = 300, minDistinctCategories = 2
Output:
[["P1","P2"],["P1","P4"],["P2","P4"],["P3","P4"]]
Note:
Valid bundles:
Example 2
Input:
products = [ { id: "A", category: "Electronics", price: 500 }, { id: "B", category: "HomeGoods", price: 300 }, { id: "C", category: "Electronics", price: 400 }, { id: "D", category: "Apparel", price: 200 }, { id: "E", category: "HomeGoods", price: 100 } ], budget = 800, minDistinctCategories = 3
Output:
[["A","D","E"],["C","D","E"]]
Note:
Valid bundles:
Example 3
Input:
products = [ { id: "X", category: "Food", price: 600 }, { id: "Y", category: "Drinks", price: 700 } ], budget = 500, minDistinctCategories = 1
Output:
[]
Note:
Neither product 'X' (price 600) nor 'Y' (price 700) can be included in any bundle, as their individual prices already exceed the budget of 500. Therefore, no valid bundles can be formed.
Constraints
1 <= products.length <= 15products[i].id is a unique non-empty string.products[i].category is a non-empty string.1 <= products[i].price <= 10001 <= budget <= 150001 <= minDistinctCategories <= 5products array will not be empty.minDistinctCategories is high.Loading editor...