This problem requires generating all possible combinations of k numbers from the range [1, n]. The order of numbers within a combination doesn't matter.

We can solve this using a backtracking algorithm. Backtracking allows us to explore different possibilities by recursively building combinations. If a combination reaches the required length (k), we add it to the result. If a path doesn't lead to a valid combination, we backtrack to explore other options.

Intuition:

Imagine building a decision tree. Each level represents choosing a number to include in our combination. At each node, we have a choice: include the current number or skip it. Backtracking helps us traverse this tree, exploring all possible paths without explicitly constructing the entire tree in memory.

We use a 'comb' list to hold the current combination being built. The 'start' parameter in the recursive function ensures that we only consider numbers greater than or equal to the last number added, preventing duplicate combinations (e.g., [1, 2] and [2, 1] are considered the same).

Step-by-step thinking:

Initialize an empty list res to store the resulting combinations.
Define a recursive function backtrack(start, comb) that takes the starting number start and the current combination comb as input.
Base case: If the length of comb is equal to k, it means we have found a valid combination. Add a copy of comb to res and return.
Iterate from start to n (inclusive). For each number i, add it to comb, and recursively call backtrack(i + 1, comb) to explore further combinations.
After the recursive call returns, remove the last added number (i) from comb. This is the backtracking step, which allows us to explore other possibilities.
Call backtrack(1, []) to start the process with an empty combination and a starting number of 1.
Finally, return the res list containing all valid combinations.

Time Complexity: O(C(n, k) * k), where C(n, k) is the binomial coefficient "n choose k". Generating each combination takes O(k) time to copy it to the result list.
Space Complexity: O(k) for the combination being built in each recursive call, plus O(C(n, k) * k) to store all the resulting combinations. The depth of the recursion is at most k.

Learn Complexity

43. Combinations

Understand Before Coding

Visualize This Problem

Draw Your Approach

Example 1:

Example 2:

Constraints:

Learn

Topics

Hint

Use Cases