Combinations

Description

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

A combination is a selection of items where the order does not matter. For instance, choosing numbers 1 and 3 is the same combination as choosing 3 and 1. You need to find every unique group of exactly k numbers that can be formed using the integers from 1 up to n (inclusive).

You may return the answer in any order.

Examples

Example 1

Input: n = 4, k = 2

Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

Explanation: We need to pick 2 numbers from {1, 2, 3, 4}. There are C(4,2) = 6 ways to do this. Each pair of numbers forms one combination. Note that [1,2] and [2,1] are the same combination since order does not matter, so we only list [1,2].

Example 2

Input: n = 1, k = 1

Output: [[1]]

Explanation: There is only one number available (1) and we need to pick exactly 1. The only combination possible is [1].

Example 3

Input: n = 5, k = 3

Output: [[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[2,4,5],[3,4,5]]

Explanation: We pick 3 numbers from {1, 2, 3, 4, 5}. There are C(5,3) = 10 ways. Each triplet is listed once because order within a combination is irrelevant.

Constraints

1 ≤ n ≤ 20
1 ≤ k ≤ n

Editorial

Brute Force

Intuition

The simplest way to think about this problem is: every number from 1 to n can either be included in a combination or excluded from it. This gives us a total of 2^n possible subsets of the range [1, n].

Imagine you have n light switches lined up, one for each number from 1 to n. Each switch can be ON (include that number) or OFF (exclude it). If you flip every possible arrangement of switches, you get every possible subset. From all those subsets, you simply keep the ones that have exactly k switches turned ON — those are your valid combinations.

This approach generates ALL subsets first, then filters. It does not care about efficiency; it is a straightforward enumeration strategy.

Step-by-Step Explanation

Let's trace through with n = 4, k = 2:

Step 1: Generate all 2^4 = 16 subsets of {1, 2, 3, 4} using bitmask enumeration. Each integer from 0 to 15 represents a subset via its binary representation.

Step 2: Bitmask 0 = 0000 → subset = {} → size 0 ≠ 2, skip.

Step 3: Bitmask 1 = 0001 → subset = {1} → size 1 ≠ 2, skip.

Step 4: Bitmask 2 = 0010 → subset = {2} → size 1 ≠ 2, skip.

Step 5: Bitmask 3 = 0011 → subset = {1, 2} → size 2 == k! Add [1, 2] to result.

Step 6: Bitmask 4 = 0100 → subset = {3} → size 1 ≠ 2, skip.

Step 7: Bitmask 5 = 0101 → subset = {1, 3} → size 2 == k! Add [1, 3] to result.

Step 8: Bitmask 6 = 0110 → subset = {2, 3} → size 2 == k! Add [2, 3] to result.

Step 9: Bitmask 7 = 0111 → subset = {1, 2, 3} → size 3 ≠ 2, skip.

Step 10: Continue through bitmasks 8–15. We find [1, 4] at mask 1001, [2, 4] at mask 1010, [3, 4] at mask 1100.

Step 11: After checking all 16 bitmasks, result = [[1,2],[1,3],[2,3],[1,4],[2,4],[3,4]].

We checked every single subset regardless of whether it had a chance of being valid. Most subsets were rejected.

Brute Force — Bitmask Enumeration of All Subsets — Watch how every bitmask from 0 to 2^n − 1 is checked, and only subsets of size k are kept as valid combinations.

Algorithm

Iterate through all integers from 0 to 2^n − 1. Each integer represents a bitmask.
For each bitmask, determine which bits are set (value 1). Each set bit at position j means include number j + 1 in the subset.
Count the number of set bits. If the count equals k, this subset is a valid combination.
Collect the valid combination and add it to the result list.
Return all collected combinations.

Code

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> result;
        // Iterate through all 2^n bitmasks
        for (int mask = 0; mask < (1 << n); mask++) {
            // Count set bits
            if (__builtin_popcount(mask) == k) {
                vector<int> combo;
                for (int j = 0; j < n; j++) {
                    if (mask & (1 << j)) {
                        combo.push_back(j + 1);
                    }
                }
                result.push_back(combo);
            }
        }
        return result;
    }
};

class Solution:
    def combine(self, n: int, k: int) -> list[list[int]]:
        result = []
        # Iterate through all 2^n bitmasks
        for mask in range(1 << n):
            # Count set bits
            if bin(mask).count('1') == k:
                combo = []
                for j in range(n):
                    if mask & (1 << j):
                        combo.append(j + 1)
                result.append(combo)
        return result

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        // Iterate through all 2^n bitmasks
        for (int mask = 0; mask < (1 << n); mask++) {
            if (Integer.bitCount(mask) == k) {
                List<Integer> combo = new ArrayList<>();
                for (int j = 0; j < n; j++) {
                    if ((mask & (1 << j)) != 0) {
                        combo.add(j + 1);
                    }
                }
                result.add(combo);
            }
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n × 2^n)

We iterate through all 2^n bitmasks. For each bitmask, we examine up to n bits to build the subset and count set bits. This gives O(n × 2^n) total work. Even though only C(n, k) subsets are valid, we still spend time examining every single bitmask.

Space Complexity: O(C(n, k) × k)

The output stores C(n, k) combinations, each of size k. Ignoring the output, auxiliary space is O(k) for building each individual combination.

Why This Approach Is Not Efficient

The brute force examines all 2^n subsets, but the vast majority are not valid. For n = 20 and k = 2, there are 2^20 = 1,048,576 subsets but only C(20, 2) = 190 valid combinations. That means 99.98% of the work is wasted.

The fundamental problem is that bitmask enumeration is blind — it generates every possible subset without any regard for whether the size constraint can be met. It builds subsets of size 0, 1, 3, 4, ... all the way to n, even though we only want size k.

We need an approach that only generates subsets of exactly size k from the start, avoiding the creation of invalid subsets entirely. Backtracking provides this by building combinations incrementally and stopping the moment we have k elements.

Better Approach - Basic Backtracking

Intuition

Instead of generating all subsets and filtering, we can build combinations one number at a time using backtracking. Think of it like filling k empty slots one by one.

Imagine you are picking a team of k players from n candidates numbered 1 through n. You stand at candidate 1 and make a decision: include them or skip them. Then you move to candidate 2 and decide again. You keep going until either:

You have picked k players (success — record this team), or
You have run out of candidates (stop — cannot form a complete team).

After recording a team or hitting a dead end, you backtrack: you undo your most recent decision and try the other path. This systematic exploration guarantees you find every valid team without generating any invalid subsets.

The key insight is that we process numbers in increasing order (1, 2, 3, ..., n), so each combination is naturally produced in sorted order and no duplicates arise.

Step-by-Step Explanation

Let's trace through n = 4, k = 2:

Step 1: Start with an empty combination [], begin from number 1.

Step 2: Include 1 → current = [1]. We need 1 more number. Recurse from 2.

Step 3: Include 2 → current = [1, 2]. Length equals k=2. Record [1, 2] as valid. Return.

Step 4: Backtrack: remove 2 → current = [1]. Skip 2, move to 3.

Step 5: Include 3 → current = [1, 3]. Length equals k=2. Record [1, 3] as valid. Return.

Step 6: Backtrack: remove 3 → current = [1]. Skip 3, move to 4.

Step 7: Include 4 → current = [1, 4]. Length equals k=2. Record [1, 4] as valid. Return.

Step 8: Backtrack: remove 4 → current = [1]. No more numbers after 4. Backtrack further: remove 1 → current = [].

Step 9: Skip 1, move to 2. Include 2 → current = [2]. Recurse from 3.

Step 10: Include 3 → current = [2, 3]. Length equals k=2. Record [2, 3]. Return.

Step 11: Backtrack: remove 3 → current = [2]. Include 4 → current = [2, 4]. Record [2, 4]. Return.

Step 12: Backtrack to current = []. Skip 2, move to 3. Include 3 → current = [3]. Recurse from 4.

Step 13: Include 4 → current = [3, 4]. Record [3, 4]. Return.

Step 14: Backtrack to []. Move to 4. Include 4 → current = [4]. Only 1 element and no more numbers. Cannot reach k=2. Dead end.

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

Basic Backtracking — Building Combinations Incrementally — Watch how the algorithm makes include/exclude decisions for each number, building combinations of exactly k elements and backtracking when a valid combination is found or a dead end is reached.

Algorithm

Define a recursive function backtrack(start, current) where start is the next number to consider and current is the combination being built.
Base case: If current has k elements, add a copy of current to the result and return.
Boundary check: If start > n, return (no more numbers available).
For each number i from start to n:
a. Append i to current.
b. Recurse with backtrack(i + 1, current).
c. Remove i from current (backtrack).
Start the recursion with backtrack(1, []).
Return the collected results.

Code

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> result;
        vector<int> current;
        backtrack(1, n, k, current, result);
        return result;
    }
    
    void backtrack(int start, int n, int k, vector<int>& current, vector<vector<int>>& result) {
        if (current.size() == k) {
            result.push_back(current);
            return;
        }
        for (int i = start; i <= n; i++) {
            current.push_back(i);
            backtrack(i + 1, n, k, current, result);
            current.pop_back();
        }
    }
};

class Solution:
    def combine(self, n: int, k: int) -> list[list[int]]:
        result = []
        current = []
        
        def backtrack(start: int) -> None:
            if len(current) == k:
                result.append(current[:])
                return
            for i in range(start, n + 1):
                current.append(i)
                backtrack(i + 1)
                current.pop()
        
        backtrack(1)
        return result

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

Complexity Analysis

Time Complexity: O(C(n, k) × k)

The algorithm generates exactly C(n, k) combinations. For each valid combination, it takes O(k) time to copy it into the result list. The recursion tree only explores paths that can lead to valid combinations, which is far fewer than the 2^n paths explored by brute force.

Space Complexity: O(k)

The recursion stack depth is at most k (since we add one element per level before reaching the base case). The current array holds at most k elements. Excluding the output, auxiliary space is O(k).

Why This Approach Is Not Efficient

The basic backtracking approach is already much better than brute force — it only generates valid combinations. However, it still explores some dead-end branches unnecessarily.

Consider n = 20, k = 5, and the current combination is [18]. At this point, we only have numbers 19 and 20 left to choose from, but we still need 4 more numbers. It is impossible to form a valid combination because there are only 2 remaining numbers but we need 4. Yet basic backtracking will still try to recurse deeper — it will add 19, then try to go further, hit the end, backtrack, add 20, hit the end, backtrack again.

This unnecessary exploration of guaranteed-to-fail paths wastes time. The optimization insight is: if the count of remaining available numbers is less than the count of numbers we still need, we can prune that branch immediately without recursing into it. This is called pruning, and it significantly reduces the number of recursive calls.

Optimal Approach - Backtracking with Pruning

Intuition

The optimal approach builds on basic backtracking but adds a critical optimization: early termination (pruning).

Think of the team-selection analogy again. Suppose you need a team of 5 and you are at candidate 18 out of 20 with only 1 person selected so far. You still need 4 more, but only candidates 18, 19, and 20 remain — just 3 people. No matter what decisions you make, you cannot fill 4 slots with 3 candidates. So you stop immediately instead of trying all possibilities.

The pruning condition is: at position start with current having size s, the remaining numbers are n - start + 1. If n - start + 1 < k - s (remaining numbers < spots to fill), there is no point in continuing. We prune this branch.

Equivalently, we can limit the loop: instead of iterating i from start to n, we iterate i from start to n - (k - current.size()) + 1. This ensures we never start a path that cannot possibly complete.

This pruning does not change the correctness or the set of results, but it dramatically reduces the number of recursive calls, especially when k is much smaller than n.

Step-by-Step Explanation

Let's trace through n = 5, k = 3 with pruning:

Step 1: Start with current = [], start = 1. We need 3 more numbers. Available: 5 numbers (1..5). Loop limit: i goes from 1 to 5 - (3-0) + 1 = 3. So i can be 1, 2, or 3 only.

Step 2: Include 1 → current = [1]. Need 2 more. Start = 2. Loop limit: 5 - (3-1) + 1 = 4. So i = 2, 3, or 4.

Step 3: Include 2 → current = [1, 2]. Need 1 more. Start = 3. Loop limit: 5 - (3-2) + 1 = 5. So i = 3, 4, or 5.

Step 4: Include 3 → current = [1, 2, 3]. Size = 3 = k. Record [1, 2, 3]. Backtrack.

Step 5: Include 4 → current = [1, 2, 4]. Record [1, 2, 4]. Backtrack.

Step 6: Include 5 → current = [1, 2, 5]. Record [1, 2, 5]. Backtrack. Done with [1, 2, *].

Step 7: Back to [1]. Include 3 → current = [1, 3]. Loop limit: 5 - 1 + 1 = 5. i = 4, 5.

Step 8: Include 4 → current = [1, 3, 4]. Record. Include 5 → current = [1, 3, 5]. Record. Done with [1, 3, *].

Step 9: Back to [1]. Include 4 → current = [1, 4]. Loop limit: 5. i = 5 only.

Step 10: Include 5 → current = [1, 4, 5]. Record. Done with [1, *].

Step 11: Back to []. Include 2 → current = [2]. Loop limit: 4. i = 3, 4.

Step 12: [2, 3, 4], [2, 3, 5], [2, 4, 5] all found.

Step 13: Back to []. Include 3 → current = [3]. Loop limit: 4, but we need 2 more. i = 4. Then [3, 4, 5] found.

Step 14: Back to []. i = 4 would need 2 more but only 4, 5 available → loop limit = 3, and 4 > 3, so the loop never executes. Pruned!

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

Backtracking with Pruning — Cutting Dead-End Branches Early — Watch how the pruning condition prevents the algorithm from exploring branches that cannot possibly lead to valid combinations, saving recursive calls.

Algorithm

Define a recursive function backtrack(start, current) where start is the next number to consider.
Base case: If current has k elements, add a copy to the result and return.
Pruning: Compute the upper bound for the loop: upper = n - (k - current.size()) + 1. This ensures enough numbers remain after the chosen number to complete the combination.
For each number i from start to upper:
a. Append i to current.
b. Recurse with backtrack(i + 1, current).
c. Remove i from current (backtrack).
Start the recursion with backtrack(1, []).
Return all collected results.

Code

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> result;
        vector<int> current;
        backtrack(1, n, k, current, result);
        return result;
    }
    
    void backtrack(int start, int n, int k, vector<int>& current, vector<vector<int>>& result) {
        if ((int)current.size() == k) {
            result.push_back(current);
            return;
        }
        // Pruning: only iterate up to a point where enough numbers remain
        int upper = n - (k - (int)current.size()) + 1;
        for (int i = start; i <= upper; i++) {
            current.push_back(i);
            backtrack(i + 1, n, k, current, result);
            current.pop_back();
        }
    }
};

class Solution:
    def combine(self, n: int, k: int) -> list[list[int]]:
        result = []
        current = []
        
        def backtrack(start: int) -> None:
            if len(current) == k:
                result.append(current[:])
                return
            # Pruning: upper bound ensures enough numbers remain
            need = k - len(current)
            upper = n - need + 1
            for i in range(start, upper + 1):
                current.append(i)
                backtrack(i + 1)
                current.pop()
        
        backtrack(1)
        return result

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> current = new ArrayList<>();
        backtrack(1, n, k, current, result);
        return result;
    }
    
    private void backtrack(int start, int n, int k, List<Integer> current, List<List<Integer>> result) {
        if (current.size() == k) {
            result.add(new ArrayList<>(current));
            return;
        }
        // Pruning: upper bound ensures enough numbers remain
        int need = k - current.size();
        int upper = n - need + 1;
        for (int i = start; i <= upper; i++) {
            current.add(i);
            backtrack(i + 1, n, k, current, result);
            current.remove(current.size() - 1);
        }
    }
}

Complexity Analysis

Time Complexity: O(C(n, k) × k)

The algorithm generates exactly C(n, k) = n! / (k! × (n−k)!) combinations. Each combination requires O(k) time to copy into the result. The pruning optimization ensures no time is wasted on branches that cannot lead to valid combinations. The total work is proportional to the output size, which is optimal — you cannot do better than O(C(n, k) × k) since that is the size of the output itself.

Space Complexity: O(k)

The recursion depth is at most k because each recursive call adds one element to the combination. The current array also holds at most k elements. Excluding the output storage, auxiliary space is O(k). If we count the output, it is O(C(n, k) × k).

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

Combinations

Description

Examples

Example 1

Example 2

Example 3

Constraints

Editorial

Brute Force

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Better Approach - Basic Backtracking

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Optimal Approach - Backtracking with Pruning

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis