Choose a Committee
EasyBacktrackingFree
Problem
A club has n members numbered 1 to n. Return every possible committee of exactly `k` members.
A committee is a set: [1, 3] and [3, 1] are the same committee and must appear only once. Return the committees in any order.
Example 1
- Input:
- n = 4, k = 2
- Output:
- [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
C(4, 2) = 6 ways to choose 2 members out of 4.
Example 2
- Input:
- n = 3, k = 3
- Output:
- [[1, 2, 3]]
Constraints
- 1 ≤ n ≤ 20
- 1 ≤ k ≤ n
- The number of committees C(n, k) fits comfortably in memory.
Hint
Show the first hint
How do you avoid producing both [1, 3] and [3, 1]?
Walkthrough
How to approach it
01Clarify before coding
- Is [1, 3] different from [3, 1]? No, committees are sets, so each must appear once.
- Can k equal n? Yes: the only committee is everyone.
- Any order requirement on the output? No.
02Brute force
Generate all 2^n subsets and keep the ones of size k.
Cost: O(n · 2^n): for n = 20, k = 2 that is a million subsets to keep only 190.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.