Show problems as
Classic problem #90MediumArrayBacktrackingBit Manipulation

Subsets II

Real-world version: Distinct Shim Stacks
Tracked in this browser only
Read Subsets II on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A machinist keeps a tray of steel shims. Each shim is stamped with its thickness deviation in microns, given by the array shims, and a deviation may be negative when the shim runs under nominal. Two shims can carry the same stamp, and the tray may hold several such twins.

To pack a gap the machinist assembles a stack by taking any number of shims off the tray, from none at all up to the entire tray. A stack behaves purely as a collection of stamps: the order the shims were lifted in changes nothing, so two stacks are the same job when they hold each stamp the same number of times. Twins stamped alike are interchangeable, which is why lifting the first twin or the second twin yields one stack, not two, while lifting both twins yields a different stack from lifting one.

Produce every stack the tray permits, each one listed exactly once and with no repeats between them. The empty stack counts as a stack. Neither the order of the stacks in your answer nor the order of the stamps inside a stack is judged.

Examples

Example 1

Input
shims = [4, -2, 4]
Output
[[], [-2], [-2, 4], [-2, 4, 4], [4], [4, 4]]

Two shims share the stamp 4. Lifting either one alone gives the same stack, so [4] appears once, while lifting both gives the separate stack [4, 4].

Example 2

Input
shims = [-7, -7, -7]
Output
[[], [-7], [-7, -7], [-7, -7, -7]]

With three identical stamps the only choice is how many to lift, which gives four stacks holding zero, one, two and three shims.

Example 3

Input
shims = [10, -10]
Output
[[], [-10], [-10, 10], [10]]

Nothing repeats here, so every combination of the two shims is already distinct.

Constraints

  • 1 <= shims.length <= 10
  • -10 <= shims[i] <= 10

The groups you return, and the values inside each group, may be in any order.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def distinct_shim_stacks(shims: list[int]) -> list[list[int]]:
Java
public List<List<Integer>> distinctShimStacks(int[] shims)

More on the same topics