[1, n].
Problem
Given two integers n and k, return all possible combinations of k numbers chosen from the range[1, n].
The numbers must be chosen without repetition, and the order of the numbers does not matter.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
n = 4
k = 2Output
[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]Solution
This solution uses Backtracking to generate all possible combinations. At each step, a number is added to the current combination, and the recursion continues with the next number.
start index ensures that a number is not selected again and prevents generating duplicate combinations in different orders, such as [1,2] and [2,1].
When the current combination contains exactly k numbers, it is added to the result.
After each recursive call, the last number is removed so that the algorithm can explore the next possible choice.
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> result = new ArrayList<>();
backtrack(1, n, k, new ArrayList<>(), result);
return result;
}
private void backtrack(int start, int n, int k,
List<Integer> current, List<List<Integer>> result) {
// A combination of size k is found.
if (current.size() == k) {
result.add(new ArrayList<>(current));
return;
}
for (int i = start; i <= n; i++) {
// Choose the current number.
current.add(i);
// Continue with the next number.
backtrack(i + 1, n, k, current, result);
// Undo the choice.
current.remove(current.size() - 1);
}
}
Complexity
There areC(n, k) possible combinations, and each combination contains k elements. Therefore, the time complexity is O(C(n, k) × k).
The recursion depth is at most
k, so the auxiliary space complexity is O(k), excluding the space required for the output.