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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public IList<IList<int>> Combine(int n, int k) {
6 var result = new List<IList<int>>();
7 Backtrack(n, k, 1, new List<int>(), result);
8 return result;
9 }
10
11 private void Backtrack(int n, int k, int start, List<int> current, IList<IList<int>> result) {
12 if (current.Count == k) {
13 result.Add(new List<int>(current));
14 return;
15 }
16 for (int i = start; i <= n; ++i) {
17 current.Add(i);
18 Backtrack(n, k, i + 1, current, result);
19 current.RemoveAt(current.Count - 1);
20 }
21 }
22
23 public static void Main(string[] args) {
24 var solution = new Solution();
25 var combinations = solution.Combine(4, 2);
26 foreach (var combo in combinations) {
27 Console.WriteLine("[{0}]", string.Join(", ", combo));
28 }
29 }
30}The C# solution uses the List class to maintain the current combination being evaluated recursively, adding completed combinations to the result list as the recursion progresses.
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.
1#include <vector>
std::vector<std::vector<int>> combine(int n, int k) {
std::vector<std::vector<int>> result;
int total = 1 << n;
for (int mask = 0; mask < total; ++mask) {
if (__builtin_popcount(mask) == k) {
std::vector<int> current;
for (int i = 0; i < n; ++i) {
if (mask & (1 << i)) {
current.push_back(i + 1);
}
}
result.push_back(current);
}
}
return result;
}
int main() {
int n = 4, k = 2;
std::vector<std::vector<int>> combinations = combine(n, k);
for (const auto& combo : combinations) {
std::cout << "[";
for (size_t i = 0; i < combo.size(); ++i) {
std::cout << combo[i];
if (i < combo.size() - 1) std::cout << ", ";
}
std::cout << "]\n";
}
return 0;
}In C++, we traverse numbers 0 to 2n-1, representing each as a bitmask. We use the __builtin_popcount function to count 1s in the mask, equating to picking elements for a combination.