Sponsored
Sponsored
This method uses a backtracking technique, where we recursively build each combination by adding numbers incrementally and backtrack whenever we've constructed combinations of size k or cannot extend further.
Time Complexity: O(C(n, k) * k), where C(n, k) is the binomial coefficient. Each combination is built in O(k) time.
Space Complexity: O(k) due to the recursion stack storing the current combination.
1function combine(n, k) {
2 const result = [];
3 const backtrack = (start, current) => {
4 if (current.length === k) {
5 result.push([...current]);
6 return;
7 }
8 for (let i = start; i <= n; i++) {
9 current.push(i);
10 backtrack(i + 1, current);
11 current.pop();
12 }
13 };
14
15 backtrack(1, []);
16 return result;
17}
18
19console.log(combine(4, 2));The JavaScript implementation uses closures to achieve backtracking. The backtrack function leverages an inner function to track the current path and recursion start, exploring every possible k-sized combination.
Bit masking provides a novel way to generate combinations by representing choice decisions (e.g., pick or skip) in binary. A bit mask is applied to the set of numbers [1...n], and for each bit position, if the bit is set, that number is included in the combination.
Time Complexity: O(2n * n), as we iterate over all possible subsets of [1...n] and check the bit count.
Space Complexity: O(C(n, k) * k) for storing all combinations.
1using System.Collections.Generic;
public class Solution {
public IList<IList<int>> Combine(int n, int k) {
var result = new List<IList<int>>();
int total = 1 << n;
for (int mask = 0; mask < total; ++mask) {
if (CountBits(mask) == k) {
var current = new List<int>();
for (int i = 0; i < n; ++i) {
if ((mask & (1 << i)) != 0) {
current.Add(i + 1);
}
}
result.Add(current);
}
}
return result;
}
private int CountBits(int n) {
int count = 0;
while (n > 0) {
count += n & 1;
n >>= 1;
}
return count;
}
public static void Main(string[] args) {
var solution = new Solution();
var combinations = solution.Combine(4, 2);
foreach (var combo in combinations) {
Console.WriteLine("[{0}]", string.Join(", ", combo));
}
}
}In C#, the solution uses custom bit counting instead of built-in operations, coupling loops with conditions to pick elements only for masks totaling k marks.