The frameworkeasyBacktracking with an ascending start index4 min · 111 of 290

Drill roster

List every crew of a fixed size a lifeboat station can field, generating each once by forcing the numbers upward and cutting branches too short to fill.

A station has to post every crew it could field on Saturday, and post each one once. The exercise is making a repeat impossible to write down in the first place.

The problem

Kellard Point lifeboat station keeps volunteers names on the call list, numbered 1 through volunteers. A drill launch takes a crew of exactly crew of them. Who sits where in the boat is decided later, so a crew is a set of names: the crew 2, 5, 1 and the crew 1, 2, 5 are one roster line, and the noticeboard shows it once.

Produce every crew the station could field, each written with its numbers in increasing order. The crews themselves may come back in any order.

Input. volunteers — an integer, the names on the call list. crew — an integer, the volunteers in one launch.

Output. A list of crews, each a list of crew numbers in increasing order, with no crew repeated.

Example.

volunteers = 5, crew = 3
  ->  [[1,2,3], [1,2,4], [1,2,5], [1,3,4], [1,3,5],
       [1,4,5], [2,3,4], [2,3,5], [2,4,5], [3,4,5]]

Ten crews. [3,1,2] is not an eleventh — it is [1,2,3] written badly.

A second example, at the two ends of the range:

volunteers = 4, crew = 4   ->  [[1,2,3,4]]
volunteers = 4, crew = 0   ->  [[]]

One way to take all four, and one way to take none of them: the empty crew. No crews and one empty crew are different answers.

Constraints.

  • 1 <= volunteers <= 20
  • 0 <= crew <= volunteers
  • Up to 184,756 crews come back, so they must not be filtered out of something much larger.

Hints

Hint 1

Two crews are the same when they hold the same names. Fix one canonical way to write a crew down, then make the recursion unable to produce any other.

Hint 2

If the crew so far ends at number 3, every remaining choice is above 3. That is a single number, and it belongs in the recursive call's signature.

Hint 3

Two seats left to fill and only volunteer 20 untried: the branch is dead before the loop body runs. The cut belongs in the loop's upper limit, not in an if.

Approach

Brute force

Enumerate every subset of the call list and keep the ones of the right size. With volunteers = 20 that is 2²⁰ = 1,048,576 subsets built and tested to yield the 1,140 crews of three. Generating ordered picks instead returns each crew crew! times and needs a deduplication pass afterwards.

The insight

Force every crew to be written in increasing order, and each crew is built exactly once — the recursion's only remaining freedom is which volunteer comes next, and it must be above the last one taken.

Backtracking enumerates without repeats only when distinct paths produce distinct answers, and ordering the picks buys exactly that: a path is its crew, sorted, so two paths that differ anywhere differ as sets. Nothing has to be compared against the crews already found.

The second half is the cut. With crew - len(boat) seats still to fill, no volunteer above volunteers - (crew - len(boat)) + 1 can start a branch that reaches full size, so that is the loop's upper bound. For volunteers = 20, crew = 18 the cut visits 1,330 nodes where the uncut recursion visits 1,048,555 — for the same 190 crews.

Algorithm

  1. Keep one shared buffer boat and a result list.
  2. extend(start): if boat holds crew names, append a copy, return.
  3. Otherwise loop name from start to volunteers - (crew - len(boat)) + 1.
  4. Append name, call extend(name + 1), pop it back off.
  5. Begin with extend(1).

Complexity

Time O(crew · C(volunteers, crew)) — the cut leaves only nodes that reach a leaf, so the tree is proportional to the number of crews, and each finished crew costs crew to copy. Space O(crew) for the buffer and the recursion, output excluded.

Solution

Python 3 · standard library22 lines · 6 test cases, all passing
"""Drill roster — backtracking over an ascending start index, with a size cut."""


def solve(volunteers, crew):
    rosters = []
    boat = []

    def extend(start):
        # invariant: boat holds names in strictly increasing order, all below
        # start, so every path down the tree writes a different crew exactly once.
        if len(boat) == crew:
            rosters.append(boat[:])
            return
        # no name above this can start a branch long enough to fill the boat
        last_usable = volunteers - (crew - len(boat)) + 1
        for name in range(start, last_usable + 1):
            boat.append(name)
            extend(name + 1)
            boat.pop()

    extend(1)
    return rosters
The cases that ran
TESTS = [
    ((5, 3), [[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5],
              [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]),
    ((4, 4), [[1, 2, 3, 4]]),
    ((4, 0), [[]]),
    ((1, 1), [[1]]),
    ((4, 1), [[1], [2], [3], [4]]),
    ((6, 5), [[1, 2, 3, 4, 5], [1, 2, 3, 4, 6], [1, 2, 3, 5, 6],
              [1, 2, 4, 5, 6], [1, 3, 4, 5, 6], [2, 3, 4, 5, 6]]),
]

Pitfalls

  • Appending boat instead of boat[:]. Every entry in the result is the same list object, and the recursion empties it on the way out, so volunteers = 5, crew = 3 returns ten empty lists.
  • Recursing on start instead of name + 1. A volunteer repeats inside one crew, which the station cannot launch; restarting at 1 is worse still, returning all 60 ordered picks for volunteers = 5, crew = 3.
  • A base case written as if boat and len(boat) == crew. It silently drops the crew = 0 answer, returning [] where [[]] is correct.

Variants

  • Gallery sweep — the same one-choice-per-level tree, but branches die on a geometric conflict and the answer is a count.
  • Pruning — the lesson behind this loop bound, and the three other kinds of cut.