Players wear the numbers 1 to n. Write all_teams(n: int, k: int) -> list[list[int]] that returns every possible team of exactly k different players.
- Write each team as its player numbers in increasing order.
- The teams themselves can come back in any order; each team must appear once.
all_teams(4, 2) # [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]] in some order
all_teams(3, 3) # [[1, 2, 3]]
all_teams(3, 1) # [[1], [2], [3]]
Constraints: 1 <= k <= n <= 25, and the answer has at most 60,000 teams. Don't use itertools.
Aim for time proportional to the size of the answer, even when the answer is small: all_teams(25, 23) has only 300 teams, while there are over 33 million sets of players to wade through if you look at every subset or wander into branches that can never fill a team.
Show hint
pick the players in increasing order, each larger than the last. If the players you have left to choose from are fewer than the seats still empty, that branch can't finish, so don't go down it.