Frontend School

Optimal Modular Unit Combinations

DSA
medium

Optimal Modular Unit Combinations

Medium
Recursion
Backtracking
Combinatorics
Arrays

Overview

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.

What you need to do / Task

You are tasked with implementing a function that identifies all unique combinations of modular units that satisfy two conditions:

  1. The sum of their volume properties must exactly match a given targetVolume.
  2. The sum of their 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.

Input & output

  • 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.

Clarifications

  • Empty units array: If units is empty, an empty array should be returned.
  • No solution: If no combination meets the criteria, an empty array should be returned.
  • Unique combinations: Combinations are unique based on the set of unit indices. E.g., [0, 1] is the same as [1, 0]. Your output should ensure this by sorting indices within each combination.
  • Large numbers: 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

1

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.

2

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.

3

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

Constraints & assumptions

  • 1 <= units.length <= 20
  • 1 <= units[i].volume, units[i].cost <= 10^9
  • 1 <= targetVolume, maxBudget <= 2 * 10^9
  • All volume and cost values are positive integers.
  • The 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.

Out of scope

  • Optimizing for extremely large units.length (e.g., > 30), which would require dynamic programming or more advanced techniques. The current constraints suggest a recursive backtracking approach.
  • Handling negative volume or cost.

What interviewers evaluate

  • Correctness: Does the solution correctly identify all valid and unique combinations?
  • Algorithmic Approach: Is a suitable recursive/backtracking algorithm employed to explore combinations efficiently within the given constraints?
  • Code Structure & Readability: Is the code well-organized, clean, and easy to understand?
  • Edge Cases: Does the solution handle edge cases such as an empty units array or no valid combinations gracefully?

Loading editor...