Combinations

Concept

LeetCode #77.
Problem: Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].
Input: n = 4, k = 2
Output: [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]

A Combination is a hybrid between a Permutation and a Subset.

• Like a Subset: The order doesn’t matter ([1, 2] is the exact same thing as [2, 1], so we only keep [1, 2]).
• Like a Permutation: It has a strictly enforced length limit (k).

The Strategy

The code for Combinations is literally identical to the code for Subsets, with exactly one difference: The Base Case.

In Subsets, we blindly pushed every single path into the result array.
In Combinations, we only push the path into the result array if its length exactly equals k. Once it hits k, we instantly return to abort the recursion and prevent it from grabbing any more numbers.

Implementation

// Time Complexity: O(k * C(n, k)) (Where C(n, k) is the mathematical combinations formula)
// Space Complexity: O(k) (The call stack never goes deeper than k frames!)

function combine(n: number, k: number): number[][] {
    const result: number[][] = [];
    const currentPath: number[] = [];

    // startIndex dictates what number we are currently looking at
    function backtrack(startIndex: number) {
        
        // 1. BASE CASE: Did we reach the required combination size?
        if (currentPath.length === k) {
            result.push([...currentPath]); // Clone and save!
            return; // STOP! Do not explore deeper.
        }

        // 2. EXPLORE: Try every number from startIndex up to n
        for (let i = startIndex; i <= n; i++) {
            
            // 3. DO: Pick the number
            currentPath.push(i);

            // 4. RECURSE: Move to the NEXT number (prevents duplicates)
            backtrack(i + 1);

            // 5. UNDO: Remove the number to try the next branch
            currentPath.pop();
        }
    }

    // The problem states the numbers are from 1 to n.
    backtrack(1); 
    
    return result;
}

The Mathematical Pruning Optimization

There is a brilliant optimization you can add to Combinations that senior engineers look for in FAANG interviews.

Imagine n = 4, k = 4. You need 4 numbers.
You start the loop. You pick 1. You pick 2. You pick 3. You pick 4. Great, [1,2,3,4].
You backtrack. The outer loop moves to i = 2.
Your path is [2]. You need 3 more numbers to satisfy k=4.
But there are only two numbers left in the pool (3 and 4)!
It is mathematically impossible to reach k=4 from this branch. The standard algorithm will plunge down anyway, realize it hit the end, and fail.

The Optimization: We can proactively abort the for loop if there aren’t enough numbers left in the pool to satisfy our k requirement.

// How many numbers do we currently have?
// currentPath.length

// How many numbers do we STILL NEED?
// k - currentPath.length

// How many numbers are left in the pool (from i to n)?
// n - i + 1

// We only run the loop if: (Numbers left in pool) >= (Numbers we still need)
// n - i + 1 >= k - currentPath.length
// Which simplifies algebraically to:
// i <= n - (k - currentPath.length) + 1

for (let i = startIndex; i <= n - (k - currentPath.length) + 1; i++) {
    // ...
}

This single line change drastically reduces the execution time by pruning thousands of doomed recursive branches instantly.

Interview Questions

Q: How does “Combination Sum” (LeetCode 39) differ from this?
A: In Combination Sum, you are given an array of candidate numbers (e.g., [2, 3, 6, 7]) and a target sum (7). You can reuse the exact same number unlimited times ([2, 2, 3]).
To allow infinite reuse, the recursive call simply changes from backtrack(i + 1) to backtrack(i). Because the index doesn’t increment, the recursion is allowed to repeatedly pick the exact same number over and over until it hits a base case (e.g., the running sum exceeds the target).