Introduction

Generating combinations means choosing k items from n items where order does not matter. In plain C, the usual approach is recursive backtracking or indexed iteration, because the language does not provide a built-in combinations utility.

Core Sections

A recursive backtracking solution

The most common pattern is to build the current combination in a temporary array and recurse forward through the input. Each recursive call decides which next element to include.

1#include <stdio.h>
2
3void print_combination(int combo[], int k) {
4    for (int i = 0; i < k; i++) {
5        printf("%d ", combo[i]);
6    }
7    printf("\n");
8}
9
10void generate(int arr[], int n, int k, int start, int depth, int combo[]) {
11    if (depth == k) {
12        print_combination(combo, k);
13        return;
14    }
15
16    for (int i = start; i <= n - (k - depth); i++) {
17        combo[depth] = arr[i];
18        generate(arr, n, k, i + 1, depth + 1, combo);
19    }
20}
21
22int main(void) {
23    int arr[] = {1, 2, 3, 4};
24    int combo[2];
25
26    generate(arr, 4, 2, 0, 0, combo);
27    return 0;
28}

This prints:

11 2
21 3
31 4
42 3
52 4
63 4

The key property is that recursive calls only consider positions after the current one, so duplicates and reordered variants are avoided.

How the bounds work

The loop condition i <= n - (k - depth) matters. It prevents useless recursion when there are not enough remaining elements to complete the combination.

At a high level:

• 'start says where the next pick may begin'
• 'depth says how many elements are already chosen'
• 'k - depth says how many picks are still needed'

That bound is what keeps the recursion correct and efficient.

Generating combinations of indexes instead of values

Sometimes you want the positions, not just the values. That is common when the actual data lives in another structure or when combinations drive further lookups.

1#include <stdio.h>
2
3void generate_indexes(int n, int k, int start, int depth, int combo[]) {
4    if (depth == k) {
5        for (int i = 0; i < k; i++) {
6            printf("%d ", combo[i]);
7        }
8        printf("\n");
9        return;
10    }
11
12    for (int i = start; i <= n - (k - depth); i++) {
13        combo[depth] = i;
14        generate_indexes(n, k, i + 1, depth + 1, combo);
15    }
16}

Using indexes makes the generator more reusable. You can later map those indexes to strings, structs, or rows in another array.

Bitmask generation for all subset sizes

If you need every subset rather than combinations of a fixed size, a bitmask loop is often simpler than recursion.

1#include <stdio.h>
2
3int main(void) {
4    int arr[] = {10, 20, 30};
5    int n = 3;
6
7    for (int mask = 0; mask < (1 << n); mask++) {
8        printf("{ ");
9        for (int i = 0; i < n; i++) {
10            if (mask & (1 << i)) {
11                printf("%d ", arr[i]);
12            }
13        }
14        printf("}\n");
15    }
16
17    return 0;
18}

This is not the best tool when you only want combinations of exactly k items, but it is handy for exhaustive subset enumeration.

When performance starts to matter

Combination generation grows quickly. Even with efficient code, the count is still combinatorial. For example, choosing 10 items from 30 already creates a large number of results. The practical concern is usually not the recursion overhead but the number of combinations you asked for.

If you are processing each combination, consider whether you can:

• stop early when a target is found
• stream results instead of storing all of them
• prune impossible branches before recursing deeper

Those changes matter much more than micro-optimizing the recursive function.

Common Pitfalls

• Forgetting that combinations ignore order and accidentally generating permutations instead.
• Using the wrong loop bound and recursing into branches that cannot finish.
• Storing every combination in memory when printing or processing them one at a time would be enough.
• Confusing value combinations with index combinations and making the function harder to reuse.
• Expecting a fast solution for very large n and k even though the output size itself is enormous.

Summary

• In C, recursive backtracking is the standard way to generate fixed-size combinations.
• The temporary combo array holds the current partial result as recursion progresses.
• Correct loop bounds prevent invalid branches and reduce wasted work.
• Bitmasking is useful when you want all subsets, not just size-k combinations.
• The real scalability limit is the number of combinations, not just the implementation details.