You are given two integers, n and k. Your task is to return all possible combinations of k numbers chosen from the range [1, n].

The result can be returned in any order.

Note: Combinations are unordered, i.e., [1, 2] and [2, 1] are considered the same combination.

Constraints:

• $1 \leq$ n $\leq 20$

• $1 \leq$ k $\leq n$

The algorithm uses a backtracking strategy to generate all possible combinations of size $k$ from the range $[1 … n]$. It builds each combination step by step, keeping a temporary list path representing the current sequence of chosen numbers. At every recursive call, the algorithm selects a new number to add to the path and then continues exploring with the next larger number. If the length of the path becomes equal to $k$, the combination is complete and is added to the result list. After exploring one choice, the algorithm backtracks by removing the last number, allowing it to try different alternatives. To avoid unnecessary work, the recursion stops early whenever the remaining numbers are too few to complete a valid combination. This pruning ensures the algorithm explores only those paths that can lead to valid results, making it efficient and systematic in covering all unique combinations without repetition.

The steps of the algorithm are as follows:

1. Create an empty list, ans, to store all valid combinations.

2. Define recursive function, backtrack(path, start), where:

   1. path stores the current partial combination.

   2. start is the smallest number that can be chosen next.

3. The base case is a complete combination: when len(path) == k, save it to ans and return.

4. Calculate remaining needs:

   1. Compute need = k - len(path) (how many more numbers are required).

   2. Compute max_start = n - need + 1 (the largest possible starting number that still leaves room to complete the combination).

5. Recursive exploration: For each number num from start to max_start:

   1. Append num to path (choose).

   2. Call backtrack(path, num + 1) (explore further).

   3. Remove num from path (backtrack/undo choice).

6. Start recursion by calling backtrack([], 1) with an empty path starting from 1.

7. After recursion finishes, return ans, which contains all valid combinations.

Let’s look at the following illustration to get a better understanding of the solution: