0168MediumArrayBacktrackingBit Manipulation

Distinct Shim Stacks

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def distinct_shim_stacks(shims: list[int]) -> list[list[int]]:

Java

public List<List<Integer>> distinctShimStacks(int[] shims)

The intended approach

Time O(n * 2^n)Space O(n * 2^n)

Sorting the tray parks equal stamps side by side, which turns the repeat problem into a local rule. Grow stacks by recursion: at each level, record the stack built so far, then try extending it with each remaining shim, and when a shim carries the same stamp as its immediate predecessor at that same level, skip it because that branch has already been explored. Twins therefore only ever enter a stack in a left-to-right run, so each distinct multiset of stamps is emitted once with no post-filtering.

Pythonentry point: distinct_shim_stacks

def distinct_shim_stacks(shims):
    # Time: O(n * 2^n) -- each surviving stack costs a copy of up to n values.
    # Space: O(n * 2^n) -- the collected stacks; the recursion itself is O(n) deep.
    shims = sorted(shims)
    n = len(shims)
    stacks = []
    picked = []

    def build(start):
        stacks.append(list(picked))
        for i in range(start, n):
            if i > start and shims[i] == shims[i - 1]:
                continue
            picked.append(shims[i])
            build(i + 1)
            picked.pop()

    build(0)
    return stacks

The obvious version

Enumerate all 2^n lift patterns with a bitmask, reduce each pattern to a sorted tuple of stamps, and let a set absorb the collisions between twins.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_distinct_shim_stacks(shims):
    n = len(shims)
    seen = set()
    for mask in range(1 << n):
        chosen = []
        for i in range(n):
            if mask & (1 << i):
                chosen.append(shims[i])
        seen.add(tuple(sorted(chosen)))
    return [list(entry) for entry in seen]

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in