Spending the voucher

A voucher must be spent exactly — no change is given, and nothing may be left on it. The shop wants every basket that lands on the number, listed once each.

The problem

A shelf holds second-hand books, each with a whole-pound price. Two books can share a price; they are different books, but a basket is described to the customer by its prices, so two baskets with the same prices in the same counts are one offer and should be printed once.

A customer holds a voucher worth a fixed amount. Find every basket whose prices add up to exactly the voucher. Each copy on the shelf may be used at most once, so a price stocked twice may appear at most twice in a basket.

Input. prices — a list of integers, the price of each copy on the shelf. voucher — an integer, the amount that must be matched exactly.

Output. A list of baskets, each a list of prices summing to voucher, with no two baskets holding the same prices in the same counts.

Example.

prices = [4, 3, 9, 3, 6, 1], voucher = 10
  ->  [1,3,6], [1,9], [3,3,4], [4,6]

[3,3,4] is legal because the shelf really holds two books at 3. There is no second [1,3,6], even though either 3 could have been the one used.

A second example, where the shelf is all one price:

prices = [2, 2, 2, 2], voucher = 4   ->  [2,2]

One basket, not six. Picking any two of the four copies gives the same offer. When nothing reaches the total — prices = [8, 3], voucher = 2 — the answer is the empty list.

Constraints.

• 1 <= len(prices) <= 20
• 1 <= prices[i] <= 50
• 1 <= voucher <= 200

Hints

Approach

Brute force

Enumerate all 2^n subsets, keep the ones summing to the voucher, sort each and drop repeats with a set. Twenty books give 1,048,576 subsets, most overshooting long before the last book is decided, and duplicates are only spotted after they have been built.

The insight

Walk the sorted prices once, subtracting as you go: a price above what remains ends the level, and a price equal to the one just tried at this level is skipped because its subtree is identical.

Both cuts need the sort. Ascending order means the first overshoot proves every later price overshoots, so the loop can break rather than continue. It also puts equal prices side by side, so i > start and prices[i] == prices[i-1] spots the second copy at this level — while i + 1 in the recursive call still lets a repeated price be used deeper down, which is what allows [3,3,4].

Algorithm

1. Sort the prices.
2. Call extend(0, voucher) with an empty basket.
3. If the remaining amount is 0, record a copy of the basket and return.
4. Loop i from start. If prices[i] > remaining, break out of the loop.
5. If i > start and prices[i] == prices[i-1], skip this copy.
6. Append the price, recurse with i + 1 and remaining - prices[i], then pop.

Complexity

Time O(n · 2^n) in the worst case — no better bound survives an adversarial shelf — but the break and the skip cut the real search far below that. Space O(n) for the basket and the recursion, excluding the output.

Solution

"""Spending the voucher — exact-sum combinations, each copy used once, no repeats."""


def solve(prices, voucher):
    ordered = sorted(prices)          # sorting enables both the early break and the skip
    baskets, basket = [], []

    def extend(start, remaining):
        if remaining == 0:
            baskets.append(list(basket))
            return
        for i in range(start, len(ordered)):
            price = ordered[i]
            if price > remaining:
                break                 # sorted, so every later price overshoots too
            # invariant: at one level each distinct price is tried once; a repeated price
            # here would rebuild a basket the first copy already produced
            if i > start and price == ordered[i - 1]:
                continue
            basket.append(price)
            extend(i + 1, remaining - price)   # i + 1: a book is never bought twice
            basket.pop()

    extend(0, voucher)
    return baskets

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

Pitfalls

• Recursing with i instead of i + 1 lets one copy be bought repeatedly, so a shelf with a single 2 produces [2,2,2,2,2] for a voucher of 10.
• Using continue where the break belongs still gives the right answer but loses the pruning, and the sort then buys you nothing on the running time.
• Checking remaining < 0 at the top of the call rather than before recursing wastes a call per dead branch and hides the break entirely.

Variants

• Donation hampers — the same sorted walk with no target at all, so every node of the search is an answer.
• Carillon peals — duplicates handled with used flags, because order matters there and position does not.