🎨Now live: Try our Free AI Image Generation Feature

Description
Given two integers n
and k
, return all possible combinations of k
numbers out of the range [1, n]
.
Intuition
The problem requires generating all possible combinations of k
numbers from a set of numbers ranging from 1
to n
. This can be efficiently achieved using a backtracking approach, which explores all potential combinations and backtracks when a solution or a dead-end is reached.
Approach
- Initialize a Result List: Start with an empty list to store all valid combinations.
- Backtracking Function: Define a helper function
backtrack
that takes the current starting index and the current combination as parameters. - Base Case: If the length of the current combination equalsk
, add it to the result list. - Recursive Case: Iterate over the numbers from the current start index ton
, add each number to the current combination, and recursively call thebacktrack
function with the next starting index. - After the recursive call, remove the last number added to the combination to explore other possibilities. - Initial Call: Call the
backtrack
function initially with the start index1
and an empty combination.
Complexity
Time Complexity:
(O(C(n, k) \cdot k)), where (C(n, k)) is the binomial coefficient representing the number of combinations. Each combination is constructed in (O(k)) time.
Space Complexity:
(O(C(n, k) \cdot k)), which accounts for the space needed to store all combinations. The recursive stack space is (O(k)).
Code
C++
class Solution {
public:
vector> combine(int n, int k) {
vector> result;
vector combination;
backtrack(n, k, 1, combination, result);
return result;
}
private:
void backtrack(int n, int k, int start, vector& combination, vector>& result) {
if (combination.size() == k) {
result.push_back(combination);
return;
}
for (int i = start; i <= n; ++i) {
combination.push_back(i);
backtrack(n, k, i + 1, combination, result);
combination.pop_back();
}
}
};
Python
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
def backtrack(start, combination):
if len(combination) == k:
result.append(combination[:])
return
for i in range(start, n + 1):
combination.append(i)
backtrack(i + 1, combination)
combination.pop()
result = []
backtrack(1, [])
return result
Java
class Solution {
public List> combine(int n, int k) {
List> result = new ArrayList<>();
List combination = new ArrayList<>();
backtrack(n, k, 1, combination, result);
return result;
}
private void backtrack(int n, int k, int start, List combination, List> result) {
if (combination.size() == k) {
result.add(new ArrayList<>(combination));
return;
}
for (int i = start; i <= n; ++i) {
combination.add(i);
backtrack(n, k, i + 1, combination, result);
combination.remove(combination.size() - 1);
}
}
}
JavaScript
var combine = (n, k) =>
{
let q = [], r = []
for(let i = 1; i <=n; i++) q.push([i])
while(q.length) {
let Q = []
q.forEach(e => {
if(e.length === k) return r.push(e)
for(let i = e[e.length - 1] + 1; i <= n; i++) Q.push([...e, i])
})
q = Q
}
return r
}