605. Choose K of N
A school has n students numbered 1 to n, and a teacher must pick a team of exactly k students. Two teams are the same if they contain the same students, whatever order they are listed in.
Return every possible team as an array of student numbers. Each team must appear exactly once. Teams may be returned in any order and the numbers inside a team may be in any order.
The work should be proportional to the number of teams times k, so do not enumerate all n! orderings.
Example 1
- Input:
- n = 4, k = 2
- Output:
- [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
- Explanation:
Six teams are possible:
[1, 2],[1, 3],[1, 4],[2, 3],[2, 4]and[3, 4].
Example 2
- Input:
- n = 3, k = 3
- Output:
- [[1,2,3]]
- Explanation:
Choosing all three students gives the single team
[1, 2, 3].
Example 3
- Input:
- n = 5, k = 1
- Output:
- [[1],[2],[3],[4],[5]]
- Explanation:
With
k = 1each student forms a team of one.
Constraints
- 1 ≤
k≤n≤ 10
How this problem is judged
- Answers
- Lists at every level may be in any order. Duplicates still count.
Expected complexity
- Time
- O(k * C(n, k))
- Space
- O(k)