Pipette doses

The rack holds a few tip sizes and the vial needs an exact volume. Listing the recipes by hand misses some and writes others twice.

The problem

A lab rack holds pipette tips in a few fixed volumes, whole microlitres, all different. The technician draws one tip at a time and empties it into the vial; a volume can be drawn as often as wanted, with no cap on the draws.

List every way to reach target microlitres exactly. Two recipes are the same when they use the same volumes the same number of times — everything lands in one vial, so 3 + 5 and 5 + 3 are one recipe. Write each with its volumes in non-decreasing order.

Input. tips — distinct positive integers, the volumes on the rack. target — the volume needed.

Output. Every recipe, a list of volumes summing to target, in any order.

Example.

tips = [2, 3, 5], target = 8

->  [[2, 2, 2, 2], [2, 3, 3], [3, 5]]

Four 2s, or a 2 and two 3s, or a 3 and a 5. 5 + 3 is not a fourth, and 2 + 2 + 5 overshoots.

A second example, where the answer is empty:

tips = [4, 6], target = 3      ->  []
tips = [2, 4, 8], target = 8   ->  [[2,2,2,2], [2,2,4], [4,4], [8]]

Nothing built from 4s and 6s lands on 3, so the answer is the empty list, not a list holding an empty recipe. A single 8 is a recipe of one draw.

Constraints.

• 1 <= len(tips) <= 20, all distinct
• 2 <= tips[i] <= 40
• 1 <= target <= 40

Hints

Approach

Brute force

Enumerate every sequence of draws whose running total lands on the target, sort each, and drop the duplicates. On the rack [2, 3, 5] with a target of 40 there are 560,287 sequences and 34 distinct recipes: sixteen thousand sequences per line of answer.

The insight

Never step backwards along the rack: after drawing the tip at index i, the next draw may reuse i or move on, but never return to an earlier index — so every branch is non-decreasing and each recipe is produced once.

The precondition is that every volume is positive: the owed volume strictly falls with each draw, so the recursion terminates, and the non-decreasing rule orders the recipes rather than filtering them afterwards. Sorting the rack buys a second thing — once a tip exceeds what is owed, so does every tip after it, so the loop can stop rather than skip.

Algorithm

1. Sort the rack.
2. draw(i, owed) — record every recipe from tips[i:] summing to owed, using the shared buffer.
3. If owed == 0, append a copy of recipe and return.
4. For j from i to the end: if tips[j] > owed, break — the rack is sorted, so nothing later fits.
5. Otherwise append tips[j], call draw(j, owed - tips[j]), then pop.

Complexity

Time O(n^(t/m)) where t is the target and m the smallest tip: no recipe holds more than t/m draws, so the tree is that deep and each node branches at most n ways. Space O(t/m) for the deepest chain of draws.

Solution

"""Pipette doses — every multiset hitting a target, via a non-decreasing rack walk."""


def solve(tips, target):
    rack = sorted(tips)
    recipes = []
    recipe = []

    def draw(i, owed):
        # invariant: `recipe` is non-decreasing, its volumes plus `owed` equal
        # the target, and every remaining draw comes from rack[i:].
        if owed == 0:
            recipes.append(list(recipe))
            return
        for j in range(i, len(rack)):
            if rack[j] > owed:
                break              # sorted rack: nothing after this one fits
            recipe.append(rack[j])
            draw(j, owed - rack[j])   # j, not j + 1: the same tip may repeat
            recipe.pop()

    draw(0, target)
    return recipes

TESTS = [
    (([2, 3, 5], 8), [[2, 2, 2, 2], [2, 3, 3], [3, 5]]),
    (([4, 6], 3), []),                       # unreachable: empty list, not [[]]
    (([2, 4, 8], 8), [[2, 2, 2, 2], [2, 2, 4], [4, 4], [8]]),
    (([7], 7), [[7]]),                       # a single draw is a recipe
    (([7], 8), []),
    (([5, 2, 3], 6), [[2, 2, 2], [3, 3]]),   # unsorted rack, same answer
]

Pitfalls

• Recursing with j + 1 on the take branch. Reuse is forbidden, so repeated volumes disappear and the example prints only [3, 5].
• Recursing from index 0 instead of j. Stepping backwards is allowed again, so [2, 3, 3] arrives as [3, 2, 3] and [3, 3, 2] too, inflating the answer by every recipe's arrangements.
• Breaking on an unsorted rack. On [5, 2, 3] the loop stops at the 5 as soon as 5 exceeds the owed volume, never reaching the 2 or the 3, and recipes vanish silently.

Variants

• Tasting flight — the same walk down a list, but each item is taken once and no total has to be hit.
• Pruning — the lesson behind the sorted break.