Statement▼
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≤ n≤20 1≤ k≤n
Solution
The algorithm uses a backtracking strategy to generate all possible combinations of size path and then continues exploring with the next larger number. If the length of the path becomes equal to
The steps of the algorithm are as follows:
Create an empty list,
ans, to store all valid combinations.Define recursive function,
backtrack(path, start), where:pathstores the current partial combination.startis the smallest number that can be chosen next.
The base case is a complete combination: when
len(path) == k, save it toansand return.Calculate remaining needs:
Compute
need = k - len(path)(how many more numbers are required).Compute
max_start = n - need + 1(the largest possible starting number that still leaves room to complete the combination).
Recursive exploration: For each number
numfromstarttomax_start:Append
numtopath(choose).Call
backtrack(path, num + 1)(explore further).Remove
numfrompath(backtrack/undo choice).
Start recursion by calling
backtrack([], 1)with an empty path starting from 1.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: