Introduction

This question mixes two related ideas that are worth separating first. "n choose k" describes combinations, where order does not matter, while "variations without repetition" usually describes ordered selections, which are closer to nPk. In code, the recursive backtracking structure is similar, but the stopping and iteration rules differ depending on whether order matters.

If You Mean Combinations: n choose k

For combinations without repetition, each result should contain k distinct elements and the order of those chosen elements should not create duplicates.

For example, with 1 2 3 4 and k = 2, the 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 and should appear only once.

A Backtracking Algorithm for Combinations

The standard recursive approach keeps:

• the original array,
• the current partial selection,
• the next index allowed,
• and how many elements have already been chosen.

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

The key line is i + 1 in the recursive call. It ensures each element can be used at most once and prevents duplicate orderings.

Why the Loop Bound Looks Strange

This loop:

for (int i = start; i <= n - (k - depth); i++)

is a pruning step. It stops the recursion from exploring branches that do not have enough remaining elements to finish a length-k combination.

Without that bound the algorithm would still be correct, but it would do unnecessary work.

If You Mean Variations: Order Matters

If by "variation" you really mean ordered selection without repetition, then 1 2 and 2 1 are different outputs. That requires a different backtracking rule because each recursive step can choose any still-unused element.

1#include <stdio.h>
2#include <stdbool.h>
3
4void print_variation(int chosen[], int k) {
5    for (int i = 0; i < k; i++) {
6        printf("%d ", chosen[i]);
7    }
8    printf("\n");
9}
10
11void variations(int values[], int n, int k, int depth, int chosen[], bool used[]) {
12    if (depth == k) {
13        print_variation(chosen, k);
14        return;
15    }
16
17    for (int i = 0; i < n; i++) {
18        if (!used[i]) {
19            used[i] = true;
20            chosen[depth] = values[i];
21            variations(values, n, k, depth + 1, chosen, used);
22            used[i] = false;
23        }
24    }
25}

This version uses a used array because order matters and the next recursive call is allowed to choose from the full set of unused elements.

Complexity

For combinations, the number of outputs is:

C(n, k) = n! / (k! (n-k)!)

For ordered variations without repetition, the number of outputs is:

P(n, k) = n! / (n-k)!

Any correct algorithm that prints every result must spend at least that much output work, so backtracking is a natural fit.

Choosing the Right Algorithm

Ask this first:

• if 1 2 and 2 1 are the same answer, you want combinations
• if they are different answers, you want ordered variations or partial permutations

The naming in textbooks and forums is not always consistent, so clarifying the output rule matters more than memorizing the label.

Common Pitfalls

The biggest pitfall is confusing combinations with permutations or ordered variations. That changes the algorithm and the output count.

Another mistake is forgetting to advance the start index in the combinations version. If you recurse with the same starting position, you can repeat elements or generate duplicates.

Developers also sometimes forget the pruning bound and then wonder why the recursion explores useless branches.

Finally, be careful with fixed-size arrays such as chosen[2] in examples. In real code, size them according to k.

Summary

• "n choose k" means combinations, where order does not matter.
• Ordered variations without repetition are a different problem and need a used array.
• Recursive backtracking is the standard and natural solution for both.
• For combinations, advance the start index so elements are not reused and duplicates are avoided.
• Clarify the required output before writing code, because the terminology is often mixed.