Donation hampers

A food bank wants a printed list of every different hamper its crate can make. Two tins of soup are interchangeable, so a list that shows the same hamper twice is a list nobody trusts.

The problem

A crate arrives holding a number of tins. Each tin is recorded as an item code, and tins sharing a code hold the same food. A hamper is any selection of tins, from the empty hamper up to the whole crate; two hampers are the same when they hold the same codes in the same counts, whichever physical tin was picked.

Produce every distinct hamper exactly once. The empty hamper counts, and so does the full crate. Order does not matter, inside a hamper or between them.

Input. tins — a list of integers, the item code on each tin in the crate. Codes repeat when the crate holds several of the same food.

Output. A list of hampers, each a list of item codes. Every distinct hamper appears once.

Example.

tins = [7, 3, 7]   ->  [], [3], [3,7], [3,7,7], [7], [7,7]

Six hampers, not eight. Picking the first tin of code 7 and picking the second give the same hamper, so [7] is listed once.

A second example, where every tin is the same food:

tins = [5, 5, 5]   ->  [], [5], [5,5], [5,5,5]

Three identical tins give four hampers — one per count — rather than the eight selections a crate of three distinct tins would give.

Constraints.

• 0 <= len(tins) <= 12
• 1 <= tins[i] <= 100
• The crate may be empty; the answer is then the single empty hamper.

Hints

Approach

Brute force

Generate all 2^n selections by taking each tin or not, turn each into a sorted tuple, and drop repeats with a set. A crate of 12 tins gives 4096 selections, each sorted and hashed — it builds duplicates and then pays to recognise them, and with heavy repetition most of that work is thrown away.

The insight

Sort the codes, and at each level of the search let only the first copy of a value start a branch — every later copy would rebuild the identical subtree.

Two tins with the same code are interchangeable, so starting a branch with tin i or with its twin j leads to the same hampers below. Sorting is the precondition: it puts equal codes side by side, so "a later copy at this level?" is the single test i > start and codes[i] == codes[i-1]. It compares indices, not the chosen prefix, which is why a repeat inside a hamper is still allowed.

Algorithm

1. Sort the codes.
2. Call extend(0) with an empty working hamper.
3. On entry, record a copy of the working hamper — it is a valid answer.
4. Loop i from start to the end. If i > start and codes[i] == codes[i-1], skip this tin.
5. Otherwise append codes[i], recurse with i + 1, then pop it back off.

Complexity

Time O(n · 2^n) in the worst case, when all codes differ — that is the size of the output, and each hamper costs its own length to copy. Space O(n) for the recursion and the working hamper, not counting the output.

Solution

"""Donation hampers — every distinct sub-selection of a multiset, by backtracking."""


def solve(tins):
    codes = sorted(tins)              # equal codes must sit next to each other to be skipped
    hampers, chosen = [], []

    def extend(start):
        # invariant: `chosen` is a complete hamper the moment we arrive here,
        # and every hamper that extends it uses only tins from index `start` on
        hampers.append(list(chosen))
        for i in range(start, len(codes)):
            # at one level, the first copy of a value owns every hamper that value starts;
            # later copies would rebuild the same multiset
            if i > start and codes[i] == codes[i - 1]:
                continue
            chosen.append(codes[i])
            extend(i + 1)
            chosen.pop()              # undo, so the next sibling starts from a clean hamper

    extend(0)
    return hampers

TESTS = [
    (([7, 3, 7],), [[], [3], [3, 7], [3, 7, 7], [7], [7, 7]]),
    (([5, 5, 5],), [[], [5], [5, 5], [5, 5, 5]]),
    (([2, 4],), [[], [2], [2, 4], [4]]),
    (([1, 1, 2, 2],), [[], [1], [1, 1], [1, 1, 2], [1, 1, 2, 2], [1, 2],
                       [1, 2, 2], [2], [2, 2]]),
    (([],), [[]]),
    (([9],), [[], [9]]),
]

Pitfalls

• Recursing with start + 1 instead of i + 1 makes the skip rule fire on the wrong comparisons and drops hampers like [7,7].
• Skipping whenever codes[i] == codes[i-1], without the i > start guard, forbids a value from following itself, so [5,5] and [5,5,5] never appear.
• Appending the working list instead of a copy stores a reference that the later pop mutates; every hamper in the output ends up empty.
• Forgetting the empty hamper — recording only at the leaves loses it.

Variants

• Carillon peals — the same duplicate-skip idea, but on orderings rather than selections, so the test looks at what is already in use.
• Spending the voucher — the same sorted-multiset walk with a running target that prunes whole branches.