[Medium] 77. Combinations

This is a classic backtracking problem that requires generating all possible combinations of k numbers chosen from the range [1, n]. The key insight is using DFS with backtracking to explore all possible paths while avoiding duplicates.

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

Example 1:

Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

Example 2:

Input: n = 1, k = 1
Output: [[1]]

Example 3:

Input: n = 3, k = 3
Output: [[1,2,3]]

Constraints

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

Clarification Questions

Before diving into the solution, here are 5 important clarifications and assumptions to discuss during an interview:

Combination definition: What is a combination? (Assumption: Selection of k elements from n elements, order doesn’t matter - {1,2} same as {2,1})
Element range: What are the available elements? (Assumption: Numbers from 1 to n inclusive - [1, 2, …, n])
Output format: Should we return all combinations or just count? (Assumption: Return all distinct combinations - list of lists)
Order requirement: Does the order of combinations matter? (Assumption: No - can return in any order, but typically lexicographic)
Empty combination: Should we include empty combination? (Assumption: No - k >= 1 per constraints, so no empty combinations)

Interview Deduction Process (20 minutes)

Step 1: Brute-Force Approach (5 minutes)

Initial Thought: “I need to generate combinations. Let me try all possible selections.”

Naive Solution: Generate all possible k-element selections from [1..n], filter duplicates.

Complexity: O(C(n,k) × k) time, O(C(n,k) × k) space

Issues:

Generates duplicates that need filtering
Doesn’t leverage ordering constraint
Inefficient duplicate handling
More complex than needed

Step 2: Semi-Optimized Approach (7 minutes)

Insight: “I can use backtracking with ordering constraint to avoid duplicates naturally.”

Improved Solution: Use backtracking (DFS). For each position, try numbers from current number+1 to n. This ensures ascending order and avoids duplicates.

Complexity: O(C(n,k) × k) time, O(k) space

Improvements:

Avoids duplicates naturally through ordering
Backtracking is natural for combinations
O(k) space for recursion stack
Handles all cases correctly

Step 3: Optimized Solution (8 minutes)

Final Optimization: “Backtracking with ordering constraint is optimal. Can optimize with early termination.”

Best Solution: Backtracking with ordering constraint is optimal. Start from current+1 in each recursive call to ensure ascending order. Early termination when not enough numbers remain.

Complexity: O(C(n,k) × k) time, O(k) space

Key Realizations:

Backtracking is natural approach for combinations
Ordering constraint prevents duplicates
O(C(n,k) × k) time is optimal - must generate all combinations
O(k) space is optimal for recursion stack

Approach

The solution uses backtracking (DFS) with the following strategy:

Base Case: When the current path has k elements, add it to the result
Early Termination: If not enough numbers remain to form a valid combination, return early
Recursive Case: For each number from first_num to n, add it to the path and recurse
Backtrack: Remove the last element before trying the next number
Avoid Duplicates: Start from i + 1 in the next recursive call to ensure ascending order

Solution in C++

Time Complexity: O(C(n,k) × k) - We generate C(n,k) combinations, each taking O(k) time
Space Complexity: O(k) - For the recursion stack and current path

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> rtn;
        vector<int> path;
        dfs(n, k, rtn, path, 1);
        return rtn;
    }

private:
    void dfs(const int n, const int k, vector<vector<int>> & rtn, vector<int>& path, int first_num) {
        if(path.size() == k) {
            rtn.push_back(path);
            return;
        }
        if (path.size() + (n - first_num + 1) < k) {
            return;
        }
        for (int i = first_num; i <= n; i++) {
            path.push_back(i);
            dfs(n, k, rtn, path, i + 1);
            path.pop_back();
        }
    }
};

Step-by-Step Example

Let’s trace through the solution with n = 4, k = 2:

Initial Call: dfs(4, 2, rtn, [], 1)

Iteration 1: i = 1

Add 1 to path: [1]
Recursive call: dfs(4, 2, rtn, [1], 2)
- i = 2: Add 2 → [1,2] → Base case hit → Add to result
- i = 3: Add 3 → [1,3] → Base case hit → Add to result
- i = 4: Add 4 → [1,4] → Base case hit → Add to result
Remove 1 from path: []

Iteration 2: i = 2

Add 2 to path: [2]
Recursive call: dfs(4, 2, rtn, [2], 3)
- i = 3: Add 3 → [2,3] → Base case hit → Add to result
- i = 4: Add 4 → [2,4] → Base case hit → Add to result
Remove 2 from path: []

Iteration 3: i = 3

Add 3 to path: [3]
Recursive call: dfs(4, 2, rtn, [3], 4)
- i = 4: Add 4 → [3,4] → Base case hit → Add to result
Remove 3 from path: []

Iteration 4: i = 4

Add 4 to path: [4]
Recursive call: dfs(4, 2, rtn, [4], 5) → No iterations (i > n)
Remove 4 from path: []

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

Key Insights

Backtracking Pattern: Add → Recurse → Remove
Avoiding Duplicates: Use first_num parameter to ensure ascending order
Early Termination: Prune branches where path.size() + (n - first_num + 1) < k
Pruning: Stop when i > n or when remaining numbers can’t form a valid combination
Base Case: When path size equals k, we have a valid combination

Backtracking Template

This problem follows the classic backtracking template:

void backtrack(parameters) {
    if (base_case) {
        // Process result
        return;
    }
    
    for (choice in choices) {
        // Make choice
        make_choice(choice);
        
        // Recurse
        backtrack(updated_parameters);
        
        // Undo choice (backtrack)
        undo_choice(choice);
    }
}

Alternative Approaches

Iterative Solution

vector<vector<int>> combine(int n, int k) {
    vector<vector<int>> result;
    vector<int> combination(k);
    
    for (int i = 0; i < k; i++) {
        combination[i] = i + 1;
    }
    
    while (true) {
        result.push_back(combination);
        
        int i = k - 1;
        while (i >= 0 && combination[i] == n - k + i + 1) {
            i--;
        }
        
        if (i < 0) break;
        
        combination[i]++;
        for (int j = i + 1; j < k; j++) {
            combination[j] = combination[j - 1] + 1;
        }
    }
    
    return result;
}

Mathematical Approach (Using Next Permutation)

vector<vector<int>> combine(int n, int k) {
    vector<vector<int>> result;
    vector<int> combination(k);
    
    // Initialize with first k numbers
    for (int i = 0; i < k; i++) {
        combination[i] = i + 1;
    }
    
    do {
        result.push_back(combination);
    } while (next_combination(combination, n, k));
    
    return result;
}

Optimization Techniques

Early Termination

void dfs(int n, int k, vector<vector<int>>& result, vector<int>& path, int start) {
    // Early termination: not enough numbers left
    if (path.size() + (n - start + 1) < k) {
        return;
    }
    
    if (path.size() == k) {
        result.push_back(path);
        return;
    }
    
    for (int i = start; i <= n; i++) {
        path.push_back(i);
        dfs(n, k, result, path, i + 1);
        path.pop_back();
    }
}

Common Mistakes

Not Backtracking: Forgetting to remove elements after recursion
Duplicate Combinations: Not using first_num parameter correctly
Index Confusion: Mixing 0-indexed and 1-indexed ranges
Base Case Errors: Incorrect termination condition

39. Combination Sum - Combinations that sum to target
40. Combination Sum II - With duplicates and constraints
216. Combination Sum III - Using digits 1-9 only
46. Permutations - All permutations instead of combinations
78. Subsets - All possible subsets

Visual Representation

For n = 4, k = 2, the recursion tree looks like:

dfs(4,2,[],1)
├── i=1: [1] → dfs(4,2,[1],2)
│   ├── i=2: [1,2] ✓
│   ├── i=3: [1,3] ✓
│   └── i=4: [1,4] ✓
├── i=2: [2] → dfs(4,2,[2],3)
│   ├── i=3: [2,3] ✓
│   └── i=4: [2,4] ✓
├── i=3: [3] → dfs(4,2,[3],4)
│   └── i=4: [3,4] ✓
└── i=4: [4] → dfs(4,2,[4],5) (no iterations)

Robina Li

[Medium] 77. Combinations

[Medium] 77. Combinations

Problem Description

Examples

Constraints

Clarification Questions

Interview Deduction Process (20 minutes)

Step 1: Brute-Force Approach (5 minutes)

Step 2: Semi-Optimized Approach (7 minutes)

Step 3: Optimized Solution (8 minutes)

Approach

Solution in C++

Step-by-Step Example

Key Insights

Backtracking Template

Alternative Approaches

Iterative Solution

Mathematical Approach (Using Next Permutation)

Optimization Techniques

Early Termination

Common Mistakes

Visual Representation

Related Posts

Recent Posts

[Medium] 77. Combinations

Problem Description

Examples

Constraints

Clarification Questions

Interview Deduction Process (20 minutes)

Step 1: Brute-Force Approach (5 minutes)

Step 2: Semi-Optimized Approach (7 minutes)

Step 3: Optimized Solution (8 minutes)

Approach

Solution in C++

Step-by-Step Example

Key Insights

Backtracking Template

Alternative Approaches

Iterative Solution

Mathematical Approach (Using Next Permutation)

Optimization Techniques

Early Termination

Common Mistakes

Related Problems

Visual Representation

Related Posts

Recent Posts