Combinations

LeetCode 77: Combinations Solution & Explanation

Problem Overview

TL;DR: Use a recursive backtracking approach to build combinations by making a binary decision for each number from $1$ to $n$: either include it in the current set or exclude it.

The LeetCode 77 problem asks us to generate all possible combinations of $k$ numbers chosen from the range $[1, n]$. Unlike permutations, the order of numbers in a combination does not matter (e.g., [1, 2] is the same as [2, 1]), and the problem asks for the result in any order. This is a classic combinatorial problem often used to test understanding of recursion and state-space tree traversal.

Brute Force Approach for Combinations

The brute force strategy for generating combinations often involves generating every possible subset of the numbers $[1, n]$ and filtering them based on their size.

Naive Logic

1. Generate the power set (all $2^n$ subsets) of the range $[1, n]$.
2. Iterate through every generated subset.
3. Check if the size of the subset is exactly equal to $k$.
4. If yes, add it to the result list.

Pseudo-code

function generateAllSubsets(index, currentSubset):
    if index > n:
        if currentSubset.size == k:
            addToResult(currentSubset)
        return

    // Include index
    currentSubset.add(index)
    generateAllSubsets(index + 1, currentSubset)
    currentSubset.removeLast()

    // Exclude index
    generateAllSubsets(index + 1, currentSubset)

Why It Fails

While this logic produces the correct answer, it is computationally inefficient.

• Time Complexity: $O(2^n)$. For $n=20$, $2^{20} \approx 10^6$ operations, which might pass, but if $k=1$, we still generate huge subsets (size 20) only to discard them.
• Inefficiency: The algorithm explores branches that are already invalid. For example, if we have already selected $k$ items, continuing to add more items to the subset is wasted effort. Similarly, if we have excluded so many items that it is impossible to reach size $k$ with the remaining numbers, we should stop immediately.

Algorithm Strategy: Backtracking Patterns

We implement the Subsets (Include/Exclude) subpattern using recursion.

1. State Management: We track the current_number (1 to $n$) we are considering and the current_combination (list of selected numbers).
2. Base Case (Success): If current_combination has size $k$, add a copy of it to the results and return.
3. Base Case (Failure/Boundary): If current_number exceeds $n$, return.
4. Recursive Step (Include):
   • Add current_number to current_combination.
   • Recursively call the function for current_number + 1.
   • Backtrack: Remove current_number from current_combination to restore the state.
5. Recursive Step (Exclude):
   • Skip current_number.
   • Recursively call the function for current_number + 1.
   • Optimization: Only take this branch if there are enough remaining numbers to fill the combination to size $k$.

Execution Flow

Let's trace n = 4, k = 2.

1. Start: index = 1, combo = [].
2. Decision at 1:
   • Include 1: combo = [1]. Recurse to index = 2.
     • Decision at 2:
       • Include 2: combo = [1, 2]. Size is $k$ (2). Add [1, 2] to result. Return.
       • Backtrack: combo becomes [1].
       • Exclude 2: Recurse to index = 3.
         • Decision at 3:
           • Include 3: combo = [1, 3]. Size is 2. Add [1, 3]. Return.
           • Exclude 3: Recurse to index = 4.
             • Include 4: combo = [1, 4]. Size is 2. Add [1, 4]. Return.
             • Exclude 4: Not enough numbers left to reach size 2. (Pruned).
   • Backtrack: combo becomes [].
   • Exclude 1: Recurse to index = 2.
     • Decision at 2:
       • Include 2: combo = [2]. Recurse to index = 3...
       • (Process continues similarly for remaining numbers).

Proof of Correctness

The algorithm is correct because it performs an exhaustive search of the valid state space defined by the constraints.

1. Completeness: The binary decision tree covers every possible subset of $[1, n]$. By traversing both "include" and "exclude" branches, we ensure no subset is missed.
2. Validity: The base case current.size() == k ensures we only store combinations of the correct length.
3. Uniqueness: Since we iterate numbers from $1$ to $n$ strictly in increasing order, we never generate permutations (e.g., we generate [1, 2] but never [2, 1]), satisfying the definition of a combination.

Pattern Reuse Notes

The Backtracking - Subsets (Include/Exclude) pattern is a fundamental technique used in several other popular interview questions:

• LeetCode 17: Letter Combinations of a Phone Number - While typically an N-ary tree, it can be conceptualized similarly as making choices at each digit.
• LeetCode 78: Subsets - This is the parent problem. It uses the exact same Include/Exclude logic but collects all nodes in the tree, not just those at depth $k$.
• LeetCode 90: Subsets II - Applies the same pattern but adds logic to handle duplicate input numbers by skipping adjacent duplicates during the "Exclude" phase or via sorting.

Reference Implementation

C++ Solution for LeetCode 77

1class Solution {
2public:
3    vector<vector<int>> combine(int n, int k) {
4        vector<vector<int>> result;
5        vector<int> current;
6        backtrack(1, n, k, current, result);
7        return result;
8    }
9
10private:
11    void backtrack(int index, int n, int k, vector<int>& current, vector<vector<int>>& result) {
12        // Base case: combination is complete
13        if (current.size() == k) {
14            result.push_back(current);
15            return;
16        }
17
18        // Base case: index out of bounds
19        if (index > n) {
20            return;
21        }
22
23        // Branch 1: Include current number
24        current.push_back(index);
25        backtrack(index + 1, n, k, current, result);
26        current.pop_back(); // Backtrack
27
28        // Branch 2: Exclude current number
29        // Optimization: Only proceed if we have enough remaining numbers to fill k
30        // Needed: k - current.size()
31        // Available after skipping 'index': n - index
32        if (n - index >= k - current.size()) {
33            backtrack(index + 1, n, k, current, result);
34        }
35    }
36};

Java Solution for LeetCode 77

1import java.util.ArrayList;
2import java.util.List;
3
4class Solution {
5    public List<List<Integer>> combine(int n, int k) {
6        List<List<Integer>> result = new ArrayList<>();
7        backtrack(1, n, k, new ArrayList<>(), result);
8        return result;
9    }
10
11    private void backtrack(int index, int n, int k, List<Integer> current, List<List<Integer>> result) {
12        // Base case: combination is complete
13        if (current.size() == k) {
14            result.add(new ArrayList<>(current)); // Deep copy required
15            return;
16        }
17
18        // Base case: index out of bounds
19        if (index > n) {
20            return;
21        }
22
23        // Branch 1: Include current number
24        current.add(index);
25        backtrack(index + 1, n, k, current, result);
26        current.remove(current.size() - 1); // Backtrack
27
28        // Branch 2: Exclude current number
29        // Optimization: Pruning check
30        // We need (k - current.size()) more elements
31        // We have (n - index) elements left if we skip 'index'
32        if (n - index >= k - current.size()) {
33            backtrack(index + 1, n, k, current, result);
34        }
35    }
36}

Python Solution for LeetCode 77

1from typing import List
2
3class Solution:
4    def combine(self, n: int, k: int) -> List[List[int]]:
5        result = []
6        
7        def backtrack(index: int, current: List[int]):
8            # Base case: combination is complete
9            if len(current) == k:
10                result.append(current[:]) # Make a copy
11                return
12            
13            # Base case: index out of bounds
14            if index > n:
15                return
16            
17            # Branch 1: Include current number
18            current.append(index)
19            backtrack(index + 1, current)
20            current.pop() # Backtrack
21            
22            # Branch 2: Exclude current number
23            # Optimization: Pruning check
24            # If we skip 'index', we have (n - index) numbers left
25            # We need (k - len(current)) numbers
26            if n - index >= k - len(current):
27                backtrack(index + 1, current)
28                
29        backtrack(1, [])
30        return result