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.
1#include <iostream>
2#include <vector>
3
4void backtrack(int n, int k, int start, std::vector<int>& current, std::vector<std::vector<int>>& result) {
5 if (current.size() == k) {
6 result.push_back(current);
7 return;
8 }
9 for (int i = start; i <= n; ++i) {
10 current.push_back(i);
11 backtrack(n, k, i + 1, current, result);
12 current.pop_back();
13 }
14}
15
16std::vector<std::vector<int>> combine(int n, int k) {
17 std::vector<std::vector<int>> result;
18 std::vector<int> current;
19 backtrack(n, k, 1, current, result);
20 return result;
21}
22
23int main() {
24 int n = 4, k = 2;
25 std::vector<std::vector<int>> combinations = combine(n, k);
26 for (const auto& combo : combinations) {
27 std::cout << "[";
28 for (size_t i = 0; i < combo.size(); ++i) {
29 std::cout << combo[i];
30 if (i < combo.size() - 1) std::cout << ", ";
31 }
32 std::cout << "]\n";
33 }
34 return 0;
35}This solution uses C++'s vector class efficiently to manage list operations, performing the recursion similar to the C solution. The backtrack function keeps expanding the current vector until a combination of size k is constructed, then it's added to the results.
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
This code generates all possible bit masks for integers from 0 to 2n-1, checking for those that have exactly k bits set. The function __builtin_popcount is used to count the number of set bits in the mask, indicating how many items in the set are chosen for a combination.