74. Combinations

Build a combination in increasing order. At each step choose the next number to be larger than the last picked (via a start index), which avoids duplicates and reordering. When the path reaches length k, it's a valid combination.

Idea

A combination is an unordered selection, so to avoid generating the same set twice (like [1,2] and [2,1]) we only ever pick numbers in increasing order. A start index enforces this: each recursive call chooses from start..n, and recursing with i+1 guarantees the next pick is strictly larger.

Algorithm

backtrack(start, path):

1. If len(path) == k, record a copy of path.
2. Otherwise, for i from start to n:
   • Choose: append i.
   • Explore: recurse with start = i + 1.
   • Un-choose: pop i.

Worked example: n = 4, k = 2

• Start 1: [1,2], [1,3], [1,4].
• Start 2: [2,3], [2,4].
• Start 3: [3,4].

Result: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]].

Complexity

• Time: O(k · C(n,k)) — one factor of k to copy each of the C(n,k) combinations.
• Space: O(k) recursion depth (plus the output).

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

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

    private void backtrack(int start, int n, int k, 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(i + 1, n, k, path, result);
            path.remove(path.size() - 1);
        }
    }
}