Introduction

Generating all k-combinations of n items means listing every subset of size k without caring about order. The standard approach in C++ is recursive backtracking, because it is direct, efficient, and easy to adapt when you need to process combinations instead of storing them all.

What a k-combination means

If the input is [1, 2, 3, 4] and k = 2, the valid combinations are:

• '[1, 2]'
• '[1, 3]'
• '[1, 4]'
• '[2, 3]'
• '[2, 4]'
• '[3, 4]'

Notice that [1, 2] and [2, 1] are the same combination. Order does not create a new result.

The total number of combinations is the binomial coefficient often written as n choose k, but the practical programming task is generating each result one by one.

Recursive backtracking solution

The most common pattern is:

1. keep a temporary combination
2. choose the next element
3. recurse
4. remove the element and continue

1#include <iostream>
2#include <vector>
3
4void generate(
5    const std::vector<int>& items,
6    int k,
7    int start,
8    std::vector<int>& current,
9    std::vector<std::vector<int>>& result)
10{
11    if (static_cast<int>(current.size()) == k) {
12        result.push_back(current);
13        return;
14    }
15
16    for (int i = start; i < static_cast<int>(items.size()); ++i) {
17        current.push_back(items[i]);
18        generate(items, k, i + 1, current, result);
19        current.pop_back();
20    }
21}
22
23int main()
24{
25    std::vector<int> items = {1, 2, 3, 4};
26    int k = 2;
27
28    std::vector<int> current;
29    std::vector<std::vector<int>> result;
30
31    generate(items, k, 0, current, result);
32
33    for (const auto& combo : result) {
34        for (int value : combo) {
35            std::cout << value << ' ';
36        }
37        std::cout << '\n';
38    }
39}

This is the standard solution because it visits each combination exactly once.

Why the start index matters

The start parameter prevents reuse of earlier elements and keeps combinations ordered. Without it, the recursion would generate permutations or duplicate work.

When the recursion chooses items[i], the next call starts at i + 1, which means every later position can only use items to the right of the current choice.

That one rule is what turns a brute-force tree into correct combination generation.

Stream combinations without storing them all

If n and k are large, storing every combination can use a lot of memory. In many cases, you only need to print or process each combination as it appears.

1#include <iostream>
2#include <vector>
3
4void generate_and_print(
5    const std::vector<int>& items,
6    int k,
7    int start,
8    std::vector<int>& current)
9{
10    if (static_cast<int>(current.size()) == k) {
11        for (int value : current) {
12            std::cout << value << ' ';
13        }
14        std::cout << '\n';
15        return;
16    }
17
18    for (int i = start; i < static_cast<int>(items.size()); ++i) {
19        current.push_back(items[i]);
20        generate_and_print(items, k, i + 1, current);
21        current.pop_back();
22    }
23}

This reduces memory pressure because only the current partial combination is kept.

Complexity and pruning

The algorithm must ultimately produce n choose k results, so the runtime is proportional to the number of combinations. That is unavoidable because you are asking for all of them.

You can still improve efficiency slightly by stopping early when not enough elements remain:

1for (int i = start; i <= static_cast<int>(items.size()) - (k - static_cast<int>(current.size())); ++i) {
2    current.push_back(items[i]);
3    generate(items, k, i + 1, current, result);
4    current.pop_back();
5}

That bound prevents recursion from exploring branches that cannot possibly reach size k.

Alternative approaches

You can also generate combinations using bitmasks or std::next_permutation on a selection mask. Those techniques are valid, but recursive backtracking is usually easier to read and customize.

Bitmask-based code becomes attractive when:

• 'n is small enough for bit operations to stay simple'
• you want a compact iterative technique
• the input is indexed rather than object-heavy

For everyday C++ code, backtracking remains the clearest starting point.

Common Pitfalls

The biggest mistake is generating permutations instead of combinations by allowing the recursion to revisit earlier positions. The start index is what prevents that.

Another issue is forgetting the memory cost of storing every combination. If the output is huge, streaming results one at a time is often the better design.

Developers also forget edge cases such as k = 0, k > n, or empty input. Decide what those should mean and handle them deliberately.

Finally, do not expect an algorithm to avoid combinatorial growth when the requirement is literally "generate all combinations." The best you can do is implement the generation cleanly and avoid unnecessary extra work.

Summary

• Use recursive backtracking to generate k-combinations cleanly in C++.
• The start index prevents duplicates and keeps order irrelevant.
• Store combinations only if you really need them all in memory.
• You can prune branches when too few elements remain to complete the combination.
• The output size is inherently combinatorial, so plan for that cost.