Combinations

Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].

You may return the answer in any order.

Example 1:

Input: n = 4, k = 2 Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]] Explanation: There are 4 choose 2 = 6 total combinations. Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.

Example 2:

Input: n = 1, k = 1 Output: [[1]] Explanation: There is 1 choose 1 = 1 total combination.

Constraints:

• 1 <= n <= 20
• 1 <= k <= n

Approach: Backtracking with a Start Index

Algorithm

1. Explore numbers from a start index upward so that each combination is strictly increasing (prevents duplicates)
2. When the current combination reaches length k, add a copy to the result
3. For each candidate starting at start, add it, recurse with start + 1, then remove it (backtrack)
4. Prune the loop early: if the remaining numbers are fewer than needed, stop

Time & Space Complexity

• Time Complexity: O(C(n, k) * k) - each of the C(n, k) combinations costs O(k) to copy
• Space Complexity: O(k) - depth of the recursion tree (the result list is not counted)

Java Implementation

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

public class Combinations {

    /**
     * Return all possible combinations of k numbers chosen from [1, n].
     * @param n Upper bound of the range
     * @param k Size of each combination
     * @return List of combinations
     */
    public static List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), 1, n, k);
        return result;
    }

    private static void backtrack(List<List<Integer>> result, List<Integer> current,
                                  int start, int n, int k) {
        if (current.size() == k) {
            result.add(new ArrayList<>(current));
            return;
        }

        // Prune: need (k - current.size()) more numbers, so i can stop at n - needed + 1
        int needed = k - current.size();
        for (int i = start; i <= n - needed + 1; i++) {
            current.add(i);
            backtrack(result, current, i + 1, n, k);
            current.remove(current.size() - 1);
        }
    }

    // Test method
    public static void main(String[] args) {
        System.out.println("Input: n = 4, k = 2");
        System.out.println("Output: " + combine(4, 2));
        // Expected: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

        System.out.println("Input: n = 1, k = 1");
        System.out.println("Output: " + combine(1, 1));
        // Expected: [[1]]
    }
}

Example Walkthrough

For n = 4, k = 2, starting from index 1:

1. Add 1, then combine with 2, 3, 4: [1,2], [1,3], [1,4]
2. Backtrack, start at 2: [2,3], [2,4]
3. Backtrack, start at 3: [3,4]

Final output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]].

Key Points

1. Order Matters in Exploration: Starting from i + 1 guarantees strictly increasing combinations, avoiding duplicates
2. Base Case: When current.size() == k, record a deep copy of the current list
3. Pruning: Stop the loop when not enough numbers remain, saving wasted recursion
4. Deep Copy: A new list is added to the result because current is mutated during backtracking
5. Combination vs Permutation: Order does not matter, so no visited array is needed