Combinations

Combinations

What is this problem about?

The Combinations interview question is the most basic form of the combination problem. Given two integers n and k, you need to return all possible combinations of k numbers chosen from the range [1, n]. Unlike the "Combination Sum" series, there is no target sum—only a target count.

Why is this asked in interviews?

Apple and Adobe ask this Backtracking interview pattern to test fundamental recursion skills. It’s a building block for more complex problems. It checks if you understand the "base case" (when the combination size is k) and how to maintain the "only increasing" order to avoid duplicates like [1, 2] and [2, 1].

Algorithmic pattern used

This is a pure Backtracking problem.

1. Maintain a current list and a start index.
2. In each step, loop from start to n.
3. Add i to current, then recursively call with start = i + 1.
4. Remove i (backtrack) and continue the loop.

Example explanation

n = 4, k = 2

1. Start at 1.
   • Pick 1. Current = [1].
   • Inner loop starts at 2.
   • Pick 2. Current = [1, 2]. (Size 2 reached! Add to result).
   • Backtrack. Current = [1].
   • Pick 3. Current = [1, 3]. (Size 2! Add).
   • Backtrack. Current = [1].
   • Pick 4. Current = [1, 4]. (Size 2! Add).
2. Backtrack to root.
3. Start at 2.
   • Pick 2. Current = [2].
   • Inner loop starts at 3.
   • Pick 3. Current = [2, 3]. (Size 2! Add). ...and so on.

Common mistakes candidates make

• Permutations vs Combinations: Returning [2, 1] in addition to [1, 2].
• Inefficient Bounds: Looping all the way to n when there aren't enough numbers left to reach size k. (A common optimization is looping only up to n - (k - current.size()) + 1).
• Memory Management: Not creating a deep copy of the current list before adding it to the final results list.

Interview preparation tip

Always remember to "copy" the current path when you reach a valid result. In many languages, if you just add the reference, your final result list will be full of empty lists (because you backtracked everything to empty).