0223MediumBacktracking

Tasting Flight Line-ups

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 cellar stores casks barrels, numbered 1 through casks. A tasting flight is a selection of exactly pour different barrels; two flights are the same flight when they draw from the same set of barrels, no matter which barrel was poured first.

Return every flight the cellar can serve. Each flight must list its barrel numbers in increasing order, and the flights themselves may be returned in any order.

Examples

Example 1

Input: casks = 5, pour = 3
Output: [[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[3,4,5],[2,4,5]]

Ten different sets of three barrels can be drawn from five, and each one is listed with its barrel numbers increasing.

Example 2

Input: casks = 3, pour = 3
Output: [[1,2,3]]

A flight of three from three barrels can only draw all of them, so there is a single flight.

Example 3

Input: casks = 2, pour = 1
Output: [[2],[1]]

Each barrel on its own is a flight of one, so both single-barrel flights are returned; the order of the flights does not matter.

Constraints

1 <= casks <= 20
1 <= pour <= casks

The values you return 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 list_flights(casks: int, pour: int) -> list[list[int]]:

Java

public List<List<Integer>> listFlights(int casks, int pour)

The intended approach

Time O(pour * C(casks, pour))Space O(pour * C(casks, pour)) for the returned flights, O(pour) beyond them

Grow one flight in increasing barrel order, always choosing the next barrel above the last one taken, and record a copy of the flight when it holds `pour` barrels. Stop the loop at the highest barrel that still leaves enough larger barrels to finish the flight, which prunes branches that can never reach the required size.

Pythonentry point: list_flights

def list_flights(casks, pour):
    flights = []
    chosen = []

    def extend(lowest):
        if len(chosen) == pour:
            flights.append(chosen[:])
            return
        still_needed = pour - len(chosen)
        for cask in range(lowest, casks - still_needed + 2):
            chosen.append(cask)
            extend(cask + 1)
            chosen.pop()

    extend(1)
    return flights

The obvious version

Enumerate every subset of the barrels as a bit pattern and keep the subsets whose size is exactly `pour`. O(2^casks * casks).

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_list_flights(casks, pour):
    flights = []
    for pattern in range(1 << casks):
        picked = [i + 1 for i in range(casks) if pattern >> i & 1]
        if len(picked) == pour:
            flights.append(picked)
    return flights

How this problem was checked

Reference solution executed against 8 test cases — 8 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