Every team of k from n players

Backtracking Junior Python 3.13+ Reviewed By Best Latest Apps

Fill the blank

Fill the blank to stop when too few players remain.

Python 3.13
n, k = 5, 3
out: list[list[int]] = []
calls = 0

def grow(start: int, team: list[int]) -> None:
    global calls
    calls += 1
    if len(team) == k:
        out.append(team[:])
        return
    need = k - len(team)
    for p in range(start, ____):
        team.append(p)
        grow(p + 1, team)
        team.pop()

grow(1, [])
print(len(out), out[-1], calls)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A n - need + 2

Right: the last useful start leaves exactly need - 1 players after it.

With 3 still needed out of players 1 to 5, the first pick can be at most 3; the bound encodes that.

Why not the others?
  • B n + 1. The same 10 teams, but 26 calls instead of 20: the extra calls start teams that cannot be filled.
  • C n - need. That cuts off valid teams: only [1, 2, 3] is found, in 4 calls.

30-second answer

Same as listing selections, but record only at size k and stop growing once there. A useful prune: stop the loop when too few players remain to fill the team. There are C(n, k) teams, each of length k, so O(k · C(n, k)) time. Apart from the output, the path takes O(k) space.

Practise saying it · 30 s. No recording, just a timer

Explain listing all teams of k.

Say your answer out loud, then check which of these points you covered:

  • Record at size k
  • Prune when too few remain
  • O(k · C(n, k))

Deep dive

The 'not enough players left' prune turns many dead branches into no work.

itertools.combinations(range(1, n + 1), k) is the library answer.

C(n, k) is largest near k = n / 2.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def teams(n: int, k: int) -> list[list[int]]:
    team: list[int] = []
    out: list[list[int]] = []

    def grow(start: int) -> None:
        if len(team) == k:
            out.append(team[:])
            return
        need = k - len(team)
        for p in range(start, n - need + 2):  # leave room for the rest
            team.append(p)
            grow(p + 1)
            team.pop()

    grow(1)
    return out

Common mistakes

  • Recording at every depth instead of only at k.
  • Letting the loop run when the remaining players cannot fill the team.

Senior take & follow-ups

Mention the remaining-players prune; it is a small, concrete optimisation.

Follow-up questions

Think of your answer first, then open the hint.

  1. What is C(10, 5)?

    Show hint

    252.

  2. How do you get the m-th team directly?

    Show hint

    Choose each member by counting how many teams start with each candidate.

What each operation costs: Depth First Search

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.