Problem 541832 · easy · Phase 05 Advanced Algorithms & Graphs

Pick a Crew of k

backtracking · combinations · recursion

A rowing club lists its members in names (all distinct) and needs a crew of exactly k members. Return every possible crew as a list of names. The order of names inside a crew does not matter and the crews may appear in any order; the same set of people must not appear twice.

Examples

Input:  names = ["ann", "bo", "cy"], k = 2
Output: [["ann", "bo"], ["ann", "cy"], ["bo", "cy"]]

Input:  names = ["ann", "bo"], k = 0
Output: [[]]

Input:  names = ["ann"], k = 2
Output: []
Explanation: not enough members for a crew of two.

Constraints

  • 0 <= len(names) <= 10, 0 <= k <= 10
  • Result size is at most C(10, 5) = 252 crews.

Goals

  • Generate combinations by only moving forward through the candidates
  • Prune when too few candidates remain to fill the crew
Starting Python…