All problems

Combinations

Medium · backtracking

You are given two integers n and k. Consider the numbers 1, 2, ..., n.

Return every way to choose exactly k different numbers from them. The order of the chosen numbers does not matter, so [1, 3] and [3, 1] are the same choice and must appear only once. Write the numbers inside each choice in ascending order. The choices themselves may be returned in any order.

Examples

Example 1

Input: n = 4, k = 2

Output: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

There are six ways to pick two of the four numbers.

Example 2

Input: n = 3, k = 3

Output: [[1, 2, 3]]

All three numbers must be chosen, so there is only one way.

Example 3

Input: n = 3, k = 1

Output: [[1], [2], [3]]

Constraints