Zepto Inventory Optimization: Batch Picking
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.
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.
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.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]]).itemWeights[i] and cartCapacity are positive integers.cartCapacity, return an empty array [].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
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].
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].
Example 3
Input:
itemWeights = [3, 4, 5], cartCapacity = 2
Output:
[]
Note:
No combination of the given item weights sums exactly to 2.
Constraints
1 <= itemWeights.length <= 1001 <= itemWeights[i] <= 1001 <= cartCapacity <= 1000itemWeights[i] and cartCapacity are integers.Loading editor...