Combinations.

Problem. Given two integers n and k, return all combinations of k numbers chosen from 1..n. For n = 4, k = 2: [1,2], [1,3], [1,4], [2,3], [2,4], [3,4]. Order within a combination doesn't matter, so [2,1] is the same as [1,2].

Brute force

Generating all 2ⁿ subsets and keeping those of size k works but wastes effort on every wrong-sized subset. We can instead enumerate only size-k combinations directly — there are C(n,k) of them.

Optimal — backtracking with a start index

Because order is irrelevant, we impose a canonical one: each combination is built in increasing value. The start index enforces this — after choosing value i, the next choice may only come from i+1..n, which guarantees we never produce [2,1] after [1,2] and never reuse an element.

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

void backtrack(int start, int n, int k, List<Integer> path, List<List<Integer>> result) {
    if (path.size() == k) {                      // complete combination
        result.add(new ArrayList<>(path));
        return;
    }
    // Pruning: need (k - path.size()) more; stop when not enough numbers remain.
    int need = k - path.size();
    for (int i = start; i <= n - need + 1; i++) {
        path.add(i);                             // choose
        backtrack(i + 1, n, k, path, result);    // explore — note i + 1, not start
        path.remove(path.size() - 1);            // unchoose
    }
}

The loop upper bound n - need + 1 is the key prune: if fewer than need numbers remain, no branch from here can reach size k, so we cut it. Passing i + 1 (not start + 1) is what advances past the just-chosen element.

There are C(n,k) leaves and each costs O(k) to copy, so the cost is O(k · C(n,k)) time, O(k) auxiliary space plus recursion depth k.