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

text
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.

Core Insight for Combinations

The transition from brute force to the optimal LeetCode 77 solution involves pruning. We can visualize the search space as a state-space tree where each level represents a number from $1$ to $n$.

The core insight is to maintain the invariant that we only explore paths that can potentially lead to a valid solution.

1. Capacity Constraint: If the current combination size reaches $k$, we record the result and backtrack immediately. We do not process further numbers.
2. Feasibility Constraint: If the number of elements currently selected plus the number of remaining candidates is less than $k$, we cannot possibly form a valid combination. We prune this branch (stop recursing).

Visual Description: Imagine a binary tree. The root represents the decision for number 1. The left edge represents "Include 1", and the right edge represents "Exclude 1".

• Moving left (Include 1): We update our state to [1] and move to decide on 2.
• Moving right (Exclude 1): Our state remains [] and we move to decide on 2.
• At any node, if our state size is $k$, it is a leaf. If we run out of numbers to pick, it is a leaf.

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.

Reference Implementation

C++ Solution for LeetCode 77

cpp
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;
    }

private:
    void backtrack(int index, int n, int k, vector<int>& current, vector<vector<int>>& result) {
        // Base case: combination is complete
        if (current.size() == k) {
            result.push_back(current);
            return;
        }

        // Base case: index out of bounds
        if (index > n) {
            return;
        }

        // Branch 1: Include current number
        current.push_back(index);
        backtrack(index + 1, n, k, current, result);
        current.pop_back(); // Backtrack

        // Branch 2: Exclude current number
        // Optimization: Only proceed if we have enough remaining numbers to fill k
        // Needed: k - current.size()
        // Available after skipping 'index': n - index
        if (n - index >= k - current.size()) {
            backtrack(index + 1, n, k, current, result);
        }
    }
};

Java Solution for LeetCode 77

java
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 index, int n, int k, List<Integer> current, List<List<Integer>> result) {
        // Base case: combination is complete
        if (current.size() == k) {
            result.add(new ArrayList<>(current)); // Deep copy required
            return;
        }

        // Base case: index out of bounds
        if (index > n) {
            return;
        }

        // Branch 1: Include current number
        current.add(index);
        backtrack(index + 1, n, k, current, result);
        current.remove(current.size() - 1); // Backtrack

        // Branch 2: Exclude current number
        // Optimization: Pruning check
        // We need (k - current.size()) more elements
        // We have (n - index) elements left if we skip 'index'
        if (n - index >= k - current.size()) {
            backtrack(index + 1, n, k, current, result);
        }
    }
}

Python Solution for LeetCode 77

python
from typing import List

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        result = []
        
        def backtrack(index: int, current: List[int]):
            # Base case: combination is complete
            if len(current) == k:
                result.append(current[:]) # Make a copy
                return
            
            # Base case: index out of bounds
            if index > n:
                return
            
            # Branch 1: Include current number
            current.append(index)
            backtrack(index + 1, current)
            current.pop() # Backtrack
            
            # Branch 2: Exclude current number
            # Optimization: Pruning check
            # If we skip 'index', we have (n - index) numbers left
            # We need (k - len(current)) numbers
            if n - index >= k - len(current):
                backtrack(index + 1, current)
                
        backtrack(1, [])
        return result

Why do I have duplicate combinations like [1,2] and [2,1]?

Mistake: Resetting the search loop to start from 1 at every recursive step, or failing to enforce order. Why: Combinations are unordered. If you allow picking 1 then 2, and later 2 then 1, you are generating permutations, not combinations. Consequence: Incorrect output size and duplicates. The pattern enforces processing numbers $1 \to n$ strictly to avoid this.