Generate Combinations

Given n integers and an integer k, return all combinations of k elements — order does not matter. The standard backtracking solution uses a path and the start-index trick to only pick forward, avoiding duplicates like [2,1] when [1,2] is already counted. This lesson covers the algorithm, LeetCode 77/78, and implementations in C, Java, and Python with trace tables.

Overview

A combination selects k items from n without regard to order. Unlike permutations, [1,2] and [2,1] are the same combination. Backtracking builds subsets of size k by always moving forward in the array.

n = 4, k = 2, nums = [1, 2, 3, 4]

              []
         /    |     \      \
        1     2      3      4
       /|\    |\     |
      2 3 4   3 4    4

Combinations: [1,2] [1,3] [1,4] [2,3] [2,4] [3,4]
Count: C(4,2) = 6

Problem Statement

Input: Integer n (elements 1 … n) and integer k.

Output: All combinations of k numbers chosen from 1 … n.

Example: n = 4, k = 2 → [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]

Count formula: C(n, k) = n! / (k! × (n−k)!)

Backtracking Algorithm

1. Maintain current path (partial combination) and a start index.
2. Base case: if len(path) == k, append a copy to result.
3. For each index i from start to n−1:
   • Append nums[i] to path.
   • Recurse with start = i + 1 (only pick later elements).
   • Backtrack: remove last element from path.

Start-Index Trick

Always recurse from i + 1, never from earlier indices. This guarantees each combination appears once in sorted order internally.

• Without it, you'd generate both [1,2] and [2,1].
• Pruning: if remaining elements n − i < k − len(path), stop early — not enough left to fill k.
• Same template extends to subsets (all sizes) by recording at every depth, not only when len == k.

Code (C, Java, Python)

Python

def combine(n, k):
    """All k-combinations of 1..n — start-index backtracking."""
    nums = list(range(1, n + 1))
    path = []
    result = []

    def backtrack(start):
        if len(path) == k:
            result.append(path[:])
            return
        for i in range(start, n):
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()

    backtrack(0)
    return result


if __name__ == "__main__":
    print(combine(4, 2))  # [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

Java

import java.util.ArrayList;
import java.util.List;

public class Combinations {

    public static void backtrack(int n, int k, int start, List<Integer> path,
                                 List<List<Integer>> result) {
        if (path.size() == k) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i <= n; i++) {
            path.add(i);
            backtrack(n, k, i + 1, path, result);
            path.remove(path.size() - 1);
        }
    }

    public static List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(n, k, 1, new ArrayList<>(), result);
        return result;
    }

    public static void main(String[] args) {
        System.out.println(combine(4, 2).size()); // 6
    }
}

C

#include <stdio.h>
#include <stdlib.h>

int path[32], path_len = 0, count = 0;

void backtrack(int n, int k, int start) {
    int i;
    if (path_len == k) { count++; return; }
    for (i = start; i <= n; i++) {
        path[path_len++] = i;
        backtrack(n, k, i + 1);
        path_len--;
    }
}

int main(void) {
    backtrack(4, 2, 1);
    printf("%d\n", count); /* 6 */
    return 0;
}

Output & Trace

All combinations for n = 4, k = 2

Partial trace — start-index backtracking

Combination counts C(n, k)

LeetCode 77 & 78

Optimizations

• Early pruning: Skip loop when n − i + 1 < k − path.size() — not enough elements left.
• Iterative generation: Build combinations via bitmask from 0 to 2^n−1 (works for small n).
• Subsets shortcut: Same start-index loop; append path copy on every recursive call.

Approach Comparison

Real-Life Applications

Interview Tips

1. Clarify: order doesn't matter → use start index, not permutations template.
2. Write backtrack(start) and always recurse with i + 1.
3. At base case, copy path — never store the mutable list reference.
4. Mention early pruning when remaining < needed.
5. Link subsets (LC 78) as “combinations for every k.”
6. Contrast with permutations — order matters there.