Combinations

Problem Description

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.

Examples

Constraints

• 1 ≤ n ≤ 20
• 1 ≤ k ≤ n

Standard Subset Selection with a Fixed Length Target

This is Subsets restricted to exactly k elements and numbers from a range. The backtracking structure is identical: iterate from the current start, pick a number, recurse, remove it. Stop collecting at depth k.

A useful pruning: if the remaining numbers in [start, n] can’t fill k - current.size() more slots, skip. Specifically, if n - start + 1 < k - current.size(), there aren’t enough numbers left to complete a combination. This prune can meaningfully reduce the search space for large n and small remaining slots.

Solution: Backtracking with Pruning

import java.util.*;

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

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

        // prune: stop if not enough numbers remain to fill k slots
        int need = k - current.size();
        for (int i = start; i <= n - need + 1; i++) {
            current.add(i);
            backtrack(n, k, i + 1, current, result);
            current.remove(current.size() - 1);
        }
    }
}

class Solution:
    def combine(self, n: int, k: int) -> list[list[int]]:
        result = []

        def backtrack(start: int, current: list[int]):
            if len(current) == k:
                result.append(current[:])
                return

            need = k - len(current)
            # prune: stop if not enough numbers remain
            for i in range(start, n - need + 2):
                current.append(i)
                backtrack(i + 1, current)
                current.pop()

        backtrack(1, [])
        return result

#include <vector>

class Solution {
public:
    std::vector<std::vector<int>> combine(int n, int k) {
        std::vector<std::vector<int>> result;
        std::vector<int> current;
        backtrack(n, k, 1, current, result);
        return result;
    }

private:
    void backtrack(int n, int k, int start,
                   std::vector<int>& current,
                   std::vector<std::vector<int>>& result) {
        if ((int)current.size() == k) {
            result.push_back(current);
            return;
        }

        int need = k - current.size();
        for (int i = start; i <= n - need + 1; i++) {
            current.push_back(i);
            backtrack(n, k, i + 1, current, result);
            current.pop_back();
        }
    }
};

Complexity Analysis:

• Time Complexity: O(C(n, k) * k). There are C(n,k) combinations and copying each takes O(k).
• Space Complexity: O(k) recursion depth.

Where it breaks: at n = 20, k = 10, C(20, 10) = 184,756 combinations. Manageable. At n = 20, k = 5, it’s only 15,504. The pruning matters most when k is close to n.

Common Mistakes

• Starting the loop at 1 on every recursive call instead of at start. Without start, you’d generate duplicates like [1,2] and [2,1].
• Off-by-one in the loop upper bound. The pruning uses n - need + 1 (inclusive). Getting this wrong either over-prunes (missing valid combinations) or under-prunes (generating incomplete ones that never reach k elements).

Frequently Asked Questions

How is this different from Combination Sum? Combinations picks exactly k items from [1, n] with no repeats. Combination Sum picks items from an arbitrary array that sum to a target, with repeats allowed.

How many combinations does combine(20, 10) produce? C(20, 10) = 184,756. The loop n - need + 1 upper bound prunes about 40% of iterations compared to iterating to n unconditionally.

← All Problems