Frontend School

Zepto Inventory Optimization: Batch Picking

DSA
medium

Zepto Inventory Optimization: Batch Picking

Medium
Backtracking
Arrays
Recursion

Overview

At Zepto, optimizing warehouse operations is crucial for maintaining our 10-minute delivery promise. One key area is batch picking, where multiple items are grouped for a single picker's route. This problem focuses on efficiently grouping items to fill a standard picking cart with a precise total weight.

What you need to do / Task

Given a list of itemWeights (representing the weight of individual items available for picking) and a cartCapacity, your task is to find all unique combinations of items whose total weight exactly matches the cartCapacity. Each item from the itemWeights list can be picked up at most once. The order of items within a combination does not matter.

Input & output

  • itemWeights: An array of positive integers, where itemWeights[i] represents the weight of the i-th item. The array may contain duplicate weight values, which represent distinct items that happen to have the same weight.
  • cartCapacity: A positive integer representing the exact total weight the picking cart must hold.
  • Return: A 2D array (or array of arrays) of integers, where each inner array represents a unique combination of item weights that sum up to cartCapacity. Each inner combination should have its elements sorted in non-decreasing order. The overall list of combinations should also be sorted lexicographically (e.g., [[1,2], [1,3]] is sorted before [[2,1]]).

Clarifications

  • All itemWeights[i] and cartCapacity are positive integers.
  • If no combination sums up to cartCapacity, return an empty array [].
  • The input itemWeights array might contain duplicate values. For example, [1, 2, 2] means there are two distinct items, both weighing 2 units. A combination like [1, 2] (using the first '2') and [1, 2] (using the second '2') should be considered the same unique combination in the output. Your algorithm must ensure that only truly unique combinations are returned.

Examples

1

Example 1

Input:

itemWeights = [10, 1, 2, 7, 6, 1, 5], cartCapacity = 8

Output:

[[1,1,6],[1,2,5],[1,7],[2,6]]

Note:

Sorted itemWeights is [1, 1, 2, 5, 6, 7, 10]. The unique combinations summing to 8 are: [1, 1, 6], [1, 2, 5], [1, 7], and [2, 6].

2

Example 2

Input:

itemWeights = [2, 5, 2, 1, 2], cartCapacity = 5

Output:

[[1,2,2],[5]]

Note:

Sorted itemWeights is [1, 2, 2, 2, 5]. The unique combinations summing to 5 are: [1, 2, 2] (using one '1' and two '2's) and [5].

3

Example 3

Input:

itemWeights = [3, 4, 5], cartCapacity = 2

Output:

[]

Note:

No combination of the given item weights sums exactly to 2.

Constraints

Constraints & assumptions

  • 1 <= itemWeights.length <= 100
  • 1 <= itemWeights[i] <= 100
  • 1 <= cartCapacity <= 1000
  • All itemWeights[i] and cartCapacity are integers.

Out of scope

  • Optimizing for the number of items in a combination (e.g., finding the shortest list of items).
  • Handling negative weights or zero capacity.
  • Real-time inventory updates or network latency.

What interviewers evaluate

  • Correctness: The solution correctly identifies all unique combinations that sum to the target capacity.
  • Algorithm Design: Demonstrates a clear understanding of backtracking, including base cases, recursive steps, and state management.
  • Efficiency: Applies appropriate pruning techniques (e.g., sorting, skipping duplicates) to avoid redundant computations and ensure the solution is not excessively slow.
  • Code Quality: Writes clean, readable, and well-structured code with proper variable naming and comments where necessary.

Loading editor...