Combinations

• Difficulty: Medium
• Topics: Backtracking
• Link: https://leetcode.com/problems/combinations/

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.

Example 1:

Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.

Example 2:

Input: n = 1, k = 1
Output: [[1]]
Explanation: There is 1 choose 1 = 1 total combination.

Constraints:

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

Solution

1. Problem Deconstruction (500+ words)

Rewrite the Problem

1. Technical Definition:
   Given integers ( n ) and ( k ) satisfying ( 1 \leq k \leq n \leq 20 ), enumerate all distinct ( k )-element subsets of the set ( {1, 2, \dots, n} ). The output is a collection of these subsets in any permutation-insensitive order (i.e., ([1,2]) and ([2,1]) are considered identical). Each subset must be represented as a list (or equivalent sequence) of its elements, typically in increasing order to avoid duplicates. The total number of subsets is the binomial coefficient ( \binom{n}{k} ).

2. Beginner-Friendly Explanation:
   Imagine you have a bag containing numbered balls from 1 to ( n ). You are asked to pick exactly ( k ) balls out of the bag. Every possible group of balls you could pick is a valid “combination.” The order in which you pick them does not matter—only which balls end up in your hand. Your task is to list all such possible groups. For example, if ( n = 4 ) and ( k = 2 ), the possible groups are: ({1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}).

3. Mathematical Formulation:
   Let ([n] = {1, 2, \dots, n}). The problem requires computing the set: [ \mathcal{C}(n,k) = { S \subseteq [n] \mid |S| = k }. ] The cardinality of (\mathcal{C}(n,k)) is given by the binomial coefficient: [ |\mathcal{C}(n,k)| = \binom{n}{k} = \frac{n!}{k!(n-k)!}. ] For constraints ( n \leq 20 ), the maximum output size occurs when ( n = 20 ) and ( k = 10 ), yielding (\binom{20}{10} = 184756) combinations.

Constraint Analysis

• (1 \leq n \leq 20):
  This small upper bound permits exponential-time algorithms (e.g., generating all (2^n) subsets) as (2^{20} = 1,048,576) operations is trivial for modern hardware. However, the output itself may be large (up to ~185k combinations), so memory and generation efficiency must still be considered. The bound also allows recursion depths up to (k) (max 20) without stack overflow concerns in most languages.

• (1 \leq k \leq n):
  Ensures well-posed combinations:

  • When (k = 1), each combination is a singleton ({i}) for (i = 1,\dots,n).
  • When (k = n), the only combination is the entire set ([n]).
  • Implicitly excludes (k = 0), which would yield the empty set (though mathematically valid, it’s not required here).

• Hidden Edge Cases:

  1. (n = 1, k = 1): Output is ([[1]]), a single combination.
  2. (n = 20, k = 20): Output is a single list of all integers from 1 to 20.
  3. (n = 20, k = 1): Output is 20 singleton lists.
  4. (n = 20, k = 10): Maximum output volume—each combination is a 10-element list; total memory usage is moderate but non-negligible (~several MB).
  5. The “any order” clause means we need not sort the outer list, but each combination is typically sorted internally to avoid duplicates.

• Algorithmic Implications:

  • The constraints validate brute-force enumeration of all subsets via bitmasks.
  • Backtracking with pruning is optimal in practice, as it generates exactly (\binom{n}{k}) combinations without exploring unnecessary branches.
  • Since (n) is tiny, even naive recursion without memoization is acceptable.

---

2. Intuition Scaffolding

Three Analogies

1. Real-World Metaphor (Committee Selection):
   You have (n) candidates for a committee, and you must select exactly (k) members. Each possible committee is a combination. The order of selection is irrelevant—only the final group matters. This mirrors the combinatorial nature of the problem.

2. Gaming Analogy (Skill Tree Allocation):
   In an RPG, your character has (n) available skills, but you can only master (k) of them. Each possible set of skills represents a different build. Exploring all combinations helps players optimize their strategy.

3. Mathematical Analogy (Binary Strings):
   Each combination corresponds to a binary string of length (n) with exactly (k) ones, where the (i)-th bit being 1 means element (i) is included. Generating combinations is equivalent to enumerating all such binary strings in lexicographic order.

Common Pitfalls

1. Generating Permutations Instead of Combinations:
   A naive approach might generate all (k)-tuples, producing both ([1,2]) and ([2,1]) as separate outputs. To avoid this, enforce a monotonic order (e.g., strictly increasing) in each combination.

2. Overlooking Pruning Opportunities:
   In backtracking, continuing to add elements when the current partial combination already has size (k) or when insufficient numbers remain to reach (k) wastes effort. Prune branches where len(current) + (n - start + 1) < k.

3. Incorrect Start Index in Recursion:
   If the recursive call does not increment the start index, combinations like ([1,1]) may appear, violating the distinctness requirement. Always pass i+1 as the next start to ensure elements are chosen only once.

4. Using Fixed-Depth Nested Loops:
   Writing (k) nested loops is infeasible because (k) is variable. Dynamic recursion or iteration is required.

5. Memory Inefficiency in Bitmask Approach:
   Storing all (2^n) subsets when only (\binom{n}{k}) are needed is wasteful. While acceptable for (n=20), it becomes prohibitive for larger (n).

---

3. Approach Encyclopedia

Approach 1: Brute-Force Bitmask Enumeration

• Idea: Generate all (2^n) subsets by iterating integers from (0) to (2^n - 1). For each, check if the number of set bits equals (k); if so, decode the mask into a combination.
• Pseudocode:

  def combine_bitmask(n, k):
      result = []
      for mask in range(1 << n):  # 2^n possible masks
          if mask.bit_count() == k:  # Python 3.8+: int.bit_count()
              comb = []
              for i in range(n):
                  if mask & (1 << i):
                      comb.append(i + 1)  # bits 0..n-1 correspond to numbers 1..n
              result.append(comb)
      return result
  

• Complexity Proof:
  • Time: (O(2^n \cdot n)): Loop over (2^n) masks; each requires iterating over (n) bits to check and build the combination. For (n=20), this is ~(20 \times 2^{20} \approx 2.1 \times 10^7) operations, well within limits.
  • Space: (O(1)) auxiliary space (excluding output). Output storage is (O(\binom{n}{k} \cdot k)).
• Visualization (n=3, k=2):

  Mask  Binary  Bits  Combination
  0     000     0     []
  1     001     1     []
  2     010     1     []
  3     011     2     [1,2]   (bits 0 and 1 set)
  4     100     1     []
  5     101     2     [1,3]
  6     110     2     [2,3]
  7     111     3     []
  Output: [[1,2], [1,3], [2,3]]
  

Approach 2: Backtracking (DFS) with Pruning

• Idea: Systematically build combinations by choosing numbers in increasing order, recursing, then backtracking. Prune when the current path cannot yield a valid combination.
• Pseudocode:

  def combine_backtrack(n, k):
      result = []
      def backtrack(start, curr):
          # Prune: if not enough numbers left to complete combination
          if len(curr) + (n - start + 1) < k:
              return
          if len(curr) == k:
              result.append(curr[:])
              return
          for num in range(start, n + 1):
              curr.append(num)
              backtrack(num + 1, curr)
              curr.pop()
      backtrack(1, [])
      return result
  

• Complexity Proof:
  • Time: (O(\binom{n}{k} \cdot k)): Each valid combination is generated exactly once, and copying it to the result takes (O(k)) time. The recursion visits more nodes (internal branches), but the total work is dominated by the leaves.
  • Space: (O(k)) for the recursion stack and current combination (excluding output).
• Visualization (n=4, k=2, pruning omitted for clarity):

  Tree rooted at start=1, curr=[]
  ├─ add 1, curr=[1]
  │   ├─ add 2, curr=[1,2] → output
  │   ├─ add 3, curr=[1,3] → output
  │   └─ add 4, curr=[1,4] → output
  ├─ add 2, curr=[2]
  │   ├─ add 3, curr=[2,3] → output
  │   └─ add 4, curr=[2,4] → output
  └─ add 3, curr=[3]
      └─ add 4, curr=[3,4] → output
  

Approach 3: Iterative Lexicographic Generation

• Idea: Start with the smallest combination ([1,2,\dots,k]) and repeatedly generate the next combination in lexicographic order by incrementing the rightmost possible element and resetting subsequent elements.
• Pseudocode:

  def combine_iterative(n, k):
      result = []
      comb = list(range(1, k + 1))  # initial combination
      result.append(comb[:])
      while True:
          # Find the rightmost index that can be incremented
          i = k - 1
          while i >= 0 and comb[i] == n - k + i + 1:
              i -= 1
          if i < 0:
              break  # all combinations generated
          comb[i] += 1
          for j in range(i + 1, k):
              comb[j] = comb[j - 1] + 1
          result.append(comb[:])
      return result
  

• Complexity Proof:
  • Time: (O(\binom{n}{k} \cdot k)): Each iteration may update up to (k) elements.
  • Space: (O(k)) for the comb array (excluding output).
• Visualization (n=5, k=3):

  Start: [1,2,3]
  Next: [1,2,4] (increment last)
  Next: [1,2,5] (increment last)
  Next: [1,3,4] (increment second-last, reset last)
  Next: [1,3,5] (increment last)
  ... until [3,4,5]
  

Approach 4: Library Function (Python’s itertools.combinations)

• Idea: Use built-in combinatorial generators.
• Pseudocode:

  from itertools import combinations
  def combine_lib(n, k):
      return [list(c) for c in combinations(range(1, n+1), k)]
  

• Complexity: Same as optimal—internally uses an iterative algorithm similar to Approach 3.

---

4. Code Deep Dive

We’ll dissect the optimal backtracking solution line by line:

from typing import List

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        # result: stores all valid combinations.
        result = []
        
        # backtrack: recursive depth-first search function.
        # start: the smallest integer we are allowed to choose next.
        #        This ensures combinations are generated in increasing order,
        #        avoiding permutations of the same set.
        # curr: the current partial combination being built.
        def backtrack(start: int, curr: List[int]):
            # Base case: if the current combination has reached size k,
            # we add a *copy* of it to the result.
            # Why copy? Because `curr` will be modified by subsequent
            # recursive calls (via append/pop).
            if len(curr) == k:
                result.append(curr[:])  # O(k) time to copy
                return
            
            # Pruning: if the remaining numbers (from `start` to `n`) are
            # insufficient to fill the combination to size k, stop.
            # This剪枝 reduces unnecessary recursion.
            # Example: n=5, k=3, start=4, curr has 1 element -> need 2 more,
            # but only numbers 4 and 5 remain (2 numbers), so it's still possible.
            # The condition is: len(curr) + (n - start + 1) >= k.
            # Rewritten as a guard:
            if len(curr) + (n - start + 1) < k:
                return
            
            # Iterate over all possible choices from `start` to `n`.
            for num in range(start, n + 1):
                # Choose `num` by appending it to the current combination.
                curr.append(num)
                # Recurse with `start = num + 1` to ensure we pick larger
                # numbers in the next step, maintaining monotonic order.
                backtrack(num + 1, curr)
                # Backtrack: remove `num` from `curr` to try the next candidate.
                curr.pop()
        
        # Initiate the recursion with start=1 (smallest number) and an empty combination.
        backtrack(1, [])
        return result

Edge Case Handling

• Example 1 (n=4, k=2):
  • The recursion builds [1,2], [1,3], [1,4], then backtracks to start=2, builds [2,3], [2,4], etc. Pruning never triggers because enough numbers remain at each step.
• Example 2 (n=1, k=1):
  • start=1, curr=[]. Loop num=1, append, len(curr)==1 → result [[1]]. Pruning condition: 0 + (1-1+1)=1 >= 1, so no prune.
• n=20, k=20:
  • Only one path: num=1,2,...,20 sequentially. Pruning prevents any early exit because at each step, len(curr) + (n-start+1) = curr_len + (20-start+1). When curr_len=10 and start=11, remaining numbers =10, sum=20 ≥20, so continues.
• n=20, k=10 (maximum output):
  • Pruning significantly reduces branches. For instance, when curr has 5 elements and start=15, remaining numbers=6, total=11 which is ≥10, so recursion continues. If start=17, remaining=4, total=9 <10 → prune.

---

5. Complexity War Room

Hardware-Aware Analysis

• For (n=20, k=10):
  • Number of combinations: (\binom{20}{10} = 184756).
  • Each combination stored as a list of 10 integers. In CPython, each integer is an object (~28 bytes), and the list has overhead. Estimated memory: (184756 \times (10 \times 8 \text{ bytes for references} + \text{list overhead}) \approx 15\text{–}20\text{ MB}). Fits comfortably in L2/L3 cache? Not entirely, but RAM is plentiful.
  • Recursion depth: at most (k=10), stack frames are tiny.
  • CPU: Generating ~185k combinations with simple loops is trivial (<0.1 seconds in Python).

Industry Comparison Table

Approach	Time Complexity	Space Complexity (excl. output)	Readability	Interview Viability
Brute Force Bitmask	(O(2^n \cdot n))	(O(1))	7/10	❌ Only for tiny n; not scalable
Backtracking (DFS)	(O(\binom{n}{k} \cdot k))	(O(k)) recursion stack	9/10	✅ Preferred, demonstrates pruning
Iterative Lexicographic	(O(\binom{n}{k} \cdot k))	(O(k))	8/10	✅ Good, shows iteration skills
itertools.combinations	(O(\binom{n}{k} \cdot k))	(O(k))	10/10 (but library)	❌ If implementation required

---

6. Pro Mode Extras

Variants Section

1. Combinations with Repetition (Multisets):

   • Problem: Choose (k) items from (n) types with unlimited repetition, order irrelevant.
   • Example: (n=2, k=2) → ([1,1], [1,2], [2,2]).
   • Modification: In backtracking, recurse with start = num (not num+1) to allow reuse.

2. Combinations Summing to a Target:

   • Add constraint: each combination must sum to a given value.
   • Solution: Add a remaining parameter and prune when sum exceeds target.

3. Generate Combinations Iterator-Style:

   • Instead of storing all combinations, yield them one by one to reduce memory.
   • Use generators: yield curr[:] in base case.

4. Next Combination Algorithm:

   • Given a combination, compute the lexicographically next one in (O(k)) time without generating all. Useful for very large (\binom{n}{k}).

5. Parallel Combination Generation:

   • For huge (n) and small (k), split the search space by fixing the first few elements and process branches in parallel.

Interview Cheat Sheet

• First Mention: Always clarify the difference between combinations (unordered) and permutations (ordered).
• Key Insight: Maintaining a start index ensures each combination is generated exactly once in sorted order.
• Pruning: Discuss the importance of pruning with the remaining numbers count—this shows algorithmic optimization awareness.
• Complexity: Frame time complexity in terms of output size: (O(\binom{n}{k} \cdot k)) is optimal because you must output that many elements.
• Testing: Walk through small examples (n=4,k=2) on the whiteboard to verify correctness.
• Edge Cases: Explicitly handle k=1, k=n, and n=1.
• Alternative: Mention that for large n and small k, iterative bitmask may be simpler, but backtracking is more general.

Final Note: The backtracking solution is the gold standard for this problem—elegant, efficient, and easily adaptable to variations.