Optimal Modular Unit Combinations
At Livspace, we design highly customized modular solutions for our clients. A critical part of this involves selecting the right set of modular units (e.g., shelves, cabinets) to fit into a specific space while adhering to design constraints and budget. This problem simulates a core algorithmic challenge in our design process: finding optimal combinations of units.
You are tasked with implementing a function that identifies all unique combinations of modular units that satisfy two conditions:
volume properties must exactly match a given targetVolume.cost properties must not exceed a given maxBudget.Each modular unit can be used at most once in any given combination. The order of units within a combination does not matter.
units: An array of objects, where each object represents a modular unit and has two properties: volume (number) and cost (number).
Example: [{ volume: 10, cost: 50 }, { volume: 20, cost: 80 }]targetVolume: A number representing the exact total volume that the selected units must occupy.maxBudget: A number representing the maximum total cost allowed for the selected units.The function should return an array of arrays. Each inner array should contain the indices of the modular units (from the original units array) that form a valid combination. The order of indices within an inner array should be ascending. The order of combinations in the outer array does not matter. If no such combinations exist, return an empty array.
units array: If units is empty, an empty array should be returned.[0, 1] is the same as [1, 0]. Your output should ensure this by sorting indices within each combination.volume, cost, targetVolume, maxBudget can be up to 2 * 10^9. Use appropriate data types to prevent overflow (e.g., number in JavaScript/TypeScript handles large integers up to 2^53 - 1 safely, which is sufficient here).Examples
Example 1
Input:
units = [{ volume: 10, cost: 50 }, { volume: 20, cost: 80 }, { volume: 30, cost: 120 }], targetVolume = 30, maxBudget = 150
Output:
[[0,1],[2]]
Note:
Combination [0, 1]: volume = 10 + 20 = 30 (matches target), cost = 50 + 80 = 130 (within budget). Combination [2]: volume = 30 (matches target), cost = 120 (within budget). Other combinations like [0] or [1] do not meet target volume. [0,2] has volume 40. [1,2] has volume 50.
Example 2
Input:
units = [{ volume: 15, cost: 60 }, { volume: 25, cost: 100 }, { volume: 10, cost: 40 }], targetVolume = 40, maxBudget = 150
Output:
[]
Note:
The only combination summing to volume 40 is [0, 1] (15+25). However, its total cost is 60+100 = 160, which exceeds the maxBudget of 150. No other combination meets both criteria.
Example 3
Input:
units = [{ volume: 5, cost: 10 }, { volume: 5, cost: 12 }, { volume: 10, cost: 20 }, { volume: 10, cost: 30 }], targetVolume = 10, maxBudget = 25
Output:
[[0,1],[2]]
Note:
Combination [0, 1]: volume = 5 + 5 = 10 (matches target), cost = 10 + 12 = 22 (within budget). Combination [2]: volume = 10 (matches target), cost = 20 (within budget). Combination [3]: volume = 10 (matches target), cost = 30 (exceeds budget). Other combinations do not meet target volume or budget.
Constraints
1 <= units.length <= 201 <= units[i].volume, units[i].cost <= 10^91 <= targetVolume, maxBudget <= 2 * 10^9volume and cost values are positive integers.units array may contain duplicate volume and cost pairs, but each object in the input array represents a distinct physical unit (i.e., units[i] is distinct from units[j] even if units[i].volume == units[j].volume and units[i].cost == units[j].cost). Therefore, we use indices to refer to unique units.units.length (e.g., > 30), which would require dynamic programming or more advanced techniques. The current constraints suggest a recursive backtracking approach.volume or cost.units array or no valid combinations gracefully?Loading editor...