Combinations

Introduction

Combinations are a fundamental concept in combinatorics where we select a subset of items from a larger set without regard to the order of selection. In the context of coding interviews and algorithms, Combinations typically refers to generating all possible combinations of a given size from a range of numbers (e.g., generating all combinations of size 2 from numbers 1 to 4).

This problem is a classic application of Backtracking, a general algorithmic technique for exploring all possible configurations of a problem. Unlike brute force, which might generate and filter, backtracking builds solutions incrementally and abandons a path as soon as it determines that the path cannot possibly lead to a valid solution.

The Backtracking Strategy

To solve the Combinations problem, we treat the decision-making process as a tree (State Space Tree):

1. Decision: At each step, we decide whether to include the current number in our combination or skip it.
2. State: We keep track of our current position in the array (startIndex) and the current combination being built (path).
3. Base Case: If the current combination has reached the desired length (k), we add it to our result list.
4. Backtrack: After exploring a path, we remove the last added element (path.pop()) to allow the algorithm to explore other possibilities.

Key Terminology

• State Space Tree: A tree representation of all possible recursive calls. Each node represents a specific state of the recursion.
• Pruning: Stopping the recursion early if the remaining elements are insufficient to fill the remaining slots in the combination.
• Path: The current subset of numbers being constructed.

Algorithm Implementation

Problem Statement

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

TypeScript Solution

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

  // Start backtracking from index 1
  backtrack(1);

  return result;

  function backtrack(startIndex: number) {
    // Base Case: If the combination is complete
    if (path.length === k) {
      result.push([...path]); // Push a copy of the path
      return;
    }

    // Optimization: Pruning
    // If we don't have enough numbers left to fill the combination, stop.
    const remainingSlots = k - path.length;
    const remainingNumbers = n - startIndex + 1;
    if (remainingNumbers < remainingSlots) {
      return;
    }

    // Iterate through potential candidates
    for (let i = startIndex; i <= n; i++) {
      // Decision: Include i
      path.push(i);

      // Recurse: Move to the next index to avoid duplicates
      backtrack(i + 1);

      // Backtrack: Undo the last decision
      path.pop();
    }
  }
}

How It Works

1. Initialization: We start with an empty path and begin the recursion at index 1.
2. Loop: We loop from the current startIndex to n.
3. Include: We add the current number to path.
4. Recurse: We call backtrack(i + 1). Notice we pass i + 1, not i. This ensures we only pick numbers after the current one, preventing duplicate combinations (e.g., [1, 2] and [2, 1] are treated as the same combination).
5. Pop: After the recursive call returns, we remove the number from path to restore the state for the next iteration of the loop.

Complexity Analysis

Time Complexity: $O(k imes C(n, k))$

• $C(n, k)$: This is the number of combinations, which is the dominant factor. It represents the total number of leaf nodes in the state space tree.
• $k$: For each valid combination, we spend $O(k)$ time copying the path into the result array.

Space Complexity: $O(k imes C(n, k))$

• Output Space: We store all combinations.
• Auxiliary Space: The recursion stack goes as deep as $n$ in the worst case, but the space for the path array is $O(k)$.

Optimization: Pruning

A crucial optimization in backtracking is pruning. In the loop above, we added a check:

if (remainingNumbers < remainingSlots) return;

This check prevents the algorithm from exploring branches where there aren't enough numbers left to complete the combination. For example, if n = 4, k = 3, and we are at index 4, there are no numbers left to form a combination of size 3.

Real-World Applications

1. Poker Hand Analysis: Determining the probability of drawing specific hands (e.g., a flush or a straight).
2. Team Selection: Choosing a committee of members from a pool of candidates where order doesn't matter.
3. Cryptography: Generating possible keys or cipher combinations.
4. Game AI: Generating all possible moves in a game tree (though often simplified with Alpha-Beta pruning).

Common Mistakes to Avoid

1. Modifying the Input Array: Never modify the input array directly inside the recursion. Always use a separate path array.
2. Forgetting path.pop(): This is the most common error. If you don't remove the last element, your path will grow indefinitely, leading to incorrect results and stack overflow.
3. Incorrect Recursion Index: Using backtrack(i) instead of backtrack(i + 1) will generate permutations instead of combinations, resulting in duplicate sets (e.g., [1, 2] and [2, 1] appearing separately).
4. Passing Reference: Always push a copy of the path ([...path]) to the result array, otherwise, all entries in the result will point to the same reference and be modified by subsequent backtracking steps.

Practice Strategy

• Start Simple: Try generating combinations of size 2 or 3 from a small set of numbers.
• Visualize: Draw the state space tree on paper to understand how the recursion explores different paths.
• Compare: Implement the same logic for Permutations (where order matters) to understand the difference in the recursion index (i vs 0 with a used array).