Dare2Solve
Given two integers n
and k
, return all possible combinations of k
numbers out of the range [1, n]
.
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.
backtrack
that takes the current starting index and the current combination as parameters.
k
, add it to the result list.n
, add each number to the current combination, and recursively call the backtrack
function with the next starting index.backtrack
function initially with the start index 1
and an empty combination.(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.
(O(C(n, k) \cdot k)), which accounts for the space needed to store all combinations. The recursive stack space is (O(k)).
class Solution {
public:
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> result;
vector<int> combination;
backtrack(n, k, 1, combination, result);
return result;
}
private:
void backtrack(int n, int k, int start, vector<int>& combination, vector<vector<int>>& 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();
}
}
};
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
class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> combination = new ArrayList<>();
backtrack(n, k, 1, combination, result);
return result;
}
private void backtrack(int n, int k, int start, List<Integer> combination, List<List<Integer>> 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);
}
}
}
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
}