Problem Description

You are given two integers n and k. Your task is to find all possible combinations of k numbers chosen from the range [1, n].

A combination is a selection of items where the order doesn't matter. For example, [1, 2] and [2, 1] are considered the same combination.

The function should return a list of all valid combinations, and you may return them in any order.

Example walkthrough:

• If n = 4 and k = 2, you need to choose 2 numbers from [1, 2, 3, 4]
• The valid combinations would be: [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]

Key points:

• Numbers are chosen from the inclusive range [1, n]
• Each combination must contain exactly k numbers
• No duplicate numbers within a single combination
• The order of combinations in the output doesn't matter
• The order of numbers within each combination doesn't matter for uniqueness (but typically returned in ascending order due to the algorithm's nature)

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• No: The problem doesn't involve nodes and edges or graph traversal. We're working with combinations of numbers from a range.

Need to solve for kth smallest/largest?

• No: We're not looking for a specific kth element; we need to generate all possible combinations.

Involves Linked Lists?

• No: The problem deals with generating combinations of integers, not linked list operations.

Does the problem have small constraints?

• Yes: The problem involves generating combinations where we need to explore all possible ways to choose k numbers from n numbers. The combinatorial nature and the need to generate all possibilities suggests we're dealing with manageable constraints (typically n and k are small enough to enumerate all combinations).

Brute force / Backtracking?

• Yes: Since we need to generate all possible combinations and explore different choices systematically (choosing or not choosing each number), backtracking is the appropriate approach. We build combinations incrementally and backtrack when we've either found a valid combination or need to explore other possibilities.

Conclusion: The flowchart correctly leads us to use a Backtracking approach. This makes sense because:

• We need to explore all possible combinations exhaustively
• We make choices (include or exclude a number) and need to undo them to try different paths
• The problem has a clear recursive structure where we build solutions incrementally
• We need to maintain state (current combination) and restore it when backtracking

Intuition

When we need to generate all combinations of k numbers from [1, n], we're essentially making a series of decisions: for each number, should we include it in our current combination or not?

Think of it like picking a team of k players from n candidates. At each step, we look at a candidate and decide: "Should this person be on the team or not?" Once we've made enough selections to form a complete team (exactly k members), we record that team. Then we backtrack to explore other possible team compositions.

The key insight is that for each number i from 1 to n, we have two choices:

1. Include it: Add number i to our current combination and continue building with the remaining numbers
2. Exclude it: Skip number i and continue building with the remaining numbers

This naturally forms a decision tree. Starting from number 1, we explore both branches (include 1 or exclude 1), then for number 2, we again explore both branches, and so on.

The backtracking pattern emerges because:

• When we include a number and explore that path, we need to "undo" that inclusion (backtrack) to explore the path where we don't include it
• We use a temporary list t to build our current combination
• When t reaches size k, we've found a valid combination and save it
• We use append() to add a number and pop() to remove it when backtracking

The recursion naturally handles the exploration of all paths. The function dfs(i) represents "starting from number i, explore all possible combinations." By calling dfs(i+1) after including or excluding number i, we systematically explore all 2^n possible selections, keeping only those with exactly k numbers.

This approach ensures we generate all combinations without duplicates, as we process numbers in order and never revisit earlier numbers.

Learn more about Backtracking patterns.

Solution Approach

The implementation uses a backtracking approach with a depth-first search (DFS) helper function. Let's walk through the key components:

Data Structures:

• ans: A list to store all valid combinations found
• t: A temporary list that acts as our current path/combination being built

Main Algorithm - DFS Function:

The dfs(i) function represents the decision point for number i. It follows this logic:

1. Base Case - Valid Combination Found:

   if len(t) == k:
       ans.append(t[:])
       return

   When our temporary list t reaches size k, we've found a valid combination. We append a copy of t to our answer (using t[:] to create a copy, not a reference).

2. Boundary Check:

   if i > n:
       return

   If we've gone beyond the range [1, n], there are no more numbers to consider, so we return.

3. Two-Choice Recursion:

   t.append(i)      # Choice 1: Include number i
   dfs(i + 1)       # Explore with i included
   t.pop()          # Backtrack: Remove i
   dfs(i + 1)       # Choice 2: Exclude number i

   This is the core backtracking pattern:

   • First, we include number i by appending it to t
   • We recursively explore all combinations that include i by calling dfs(i + 1)
   • We backtrack by removing i from t using pop()
   • We explore all combinations that exclude i by calling dfs(i + 1) again

Execution Flow:

Starting with dfs(1), the algorithm explores a binary decision tree where each level represents a number from 1 to n. At each node, we branch into two paths: one where we include the current number and one where we don't.

For example, with n=4, k=2:

• Start at 1: Include 1 or skip 1
• If we include 1, move to 2: Include 2 (get [1,2]) or skip 2
• If we skip 2, move to 3: Include 3 (get [1,3]) or skip 3
• And so on...

Time Complexity: O(C(n,k) × k) where C(n,k) is the number of combinations. We generate C(n,k) combinations, and for each, we spend O(k) time to copy it to the answer.

Space Complexity: O(k) for the recursion stack and temporary list t, not counting the output space.

The beauty of this approach is its simplicity - by systematically making include/exclude decisions for each number and using backtracking to explore all paths, we naturally generate all possible combinations without duplicates or missing any valid combination.

Example Walkthrough

Let's trace through the algorithm with n = 3 and k = 2 to find all 2-number combinations from [1, 2, 3].

Initial Setup:

• ans = [] (stores final combinations)
• t = [] (current combination being built)
• Start with dfs(1)

Step-by-step execution:

dfs(1): t = []
├─ Include 1: t = [1]
│  └─ dfs(2): t = [1]
│     ├─ Include 2: t = [1, 2]
│     │  └─ dfs(3): len(t) = 2 = k ✓
│     │     └─ Add [1, 2] to ans, return
│     │  └─ Backtrack: t = [1]
│     └─ Exclude 2:
│        └─ dfs(3): t = [1]
│           ├─ Include 3: t = [1, 3]
│           │  └─ dfs(4): len(t) = 2 = k ✓
│           │     └─ Add [1, 3] to ans, return
│           │  └─ Backtrack: t = [1]
│           └─ Exclude 3:
│              └─ dfs(4): i > n, return
│  └─ Backtrack: t = []
└─ Exclude 1: t = []
   └─ dfs(2): t = []
      ├─ Include 2: t = [2]
      │  └─ dfs(3): t = [2]
      │     ├─ Include 3: t = [2, 3]
      │     │  └─ dfs(4): len(t) = 2 = k ✓
      │     │     └─ Add [2, 3] to ans, return
      │     │  └─ Backtrack: t = [2]
      │     └─ Exclude 3:
      │        └─ dfs(4): i > n, return
      │  └─ Backtrack: t = []
      └─ Exclude 2:
         └─ dfs(3): t = []
            ├─ Include 3: t = [3]
            │  └─ dfs(4): t = [3], len(t) = 1 < k
            │     └─ i > n, return (can't form valid combination)
            │  └─ Backtrack: t = []
            └─ Exclude 3:
               └─ dfs(4): i > n, return

Key observations from the walkthrough:

1. Include/Exclude Pattern: At each number, we first try including it (append to t), explore all possibilities, then backtrack (pop from t) and explore excluding it.

2. Valid Combinations Found:

   • [1, 2] - found when we included 1, then included 2
   • [1, 3] - found when we included 1, excluded 2, then included 3
   • [2, 3] - found when we excluded 1, included 2, then included 3

3. Pruning: When we reach i > n or len(t) == k, we stop exploring further.

4. Backtracking in Action: After finding [1, 2], we pop 2 to get back to [1], allowing us to explore [1, 3]. Similarly, we pop 1 to get back to [] to explore combinations starting with 2.

Final Result: ans = [[1, 2], [1, 3], [2, 3]]

This systematic exploration ensures we find all combinations exactly once, with no duplicates and no missed combinations.

Solution Implementation

Time and Space Complexity

Time Complexity: O(2^n)

The algorithm explores a binary decision tree where at each step (for each number from 1 to n), we make two choices: either include the current number or exclude it. This creates a complete binary tree of height n, resulting in 2^n total recursive calls. Even though we terminate early when len(t) == k, in the worst case we still explore O(2^n) nodes of the decision tree.

Space Complexity: O(n)

The space complexity consists of:

• Recursion stack depth: O(n) in the worst case, as we can go up to n levels deep in the recursion
• The temporary list t: O(k) space, which stores at most k elements
• The answer list ans: O(C(n,k) * k) space to store all combinations, where C(n,k) is the binomial coefficient representing the number of combinations

If we only consider auxiliary space (excluding the output), the space complexity is O(n) dominated by the recursion stack. If we include the output space, it becomes O(C(n,k) * k) where C(n,k) = n!/(k!(n-k)!).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Appending Reference Instead of Copy

The Pitfall: One of the most frequent mistakes is appending the temporary list directly to the result without creating a copy:

if len(current_combination) == k:
    result.append(current_combination)  # WRONG! Appends a reference
    return

Why it's problematic: Since current_combination is modified throughout the backtracking process, all entries in result will end up pointing to the same list object. When the algorithm finishes, result will contain multiple references to the same empty list (after all elements have been popped during backtracking).

The Solution: Always append a copy of the current combination:

if len(current_combination) == k:
    result.append(current_combination[:])  # Creates a new list
    # Alternative: result.append(list(current_combination))
    return

2. Inefficient Exploration Without Pruning

The Pitfall: Not implementing early termination when it's impossible to form a valid combination:

def backtrack(start, current_combination):
    if len(current_combination) == k:
        result.append(current_combination[:])
        return
  
    # Missing optimization: continuing even when there aren't enough numbers left
    for i in range(start, n + 1):
        current_combination.append(i)
        backtrack(i + 1, current_combination)
        current_combination.pop()

The Solution: Add pruning to avoid exploring paths that cannot lead to valid combinations:

def backtrack(start, current_combination):
    if len(current_combination) == k:
        result.append(current_combination[:])
        return
  
    # Pruning: check if we have enough numbers left to form a combination
    remaining_needed = k - len(current_combination)
    remaining_available = n - start + 1
    if remaining_needed > remaining_available:
        return
  
    for i in range(start, n + 1):
        current_combination.append(i)
        backtrack(i + 1, current_combination)
        current_combination.pop()

3. Using the Wrong Starting Index

The Pitfall: Starting from index 0 or using the wrong indexing in recursive calls:

def backtrack(start, current_combination):
    # ... base cases ...
  
    for i in range(start, n):  # WRONG! Missing n itself
        current_combination.append(i)
        backtrack(i, current_combination)  # WRONG! Should be i + 1
        current_combination.pop()

Why it's problematic:

• Using range(start, n) excludes n from possible selections
• Using backtrack(i, ...) instead of backtrack(i + 1, ...) allows duplicate selections of the same number

The Solution: Ensure correct range boundaries and increment properly:

for i in range(start, n + 1):  # Include n
    current_combination.append(i)
    backtrack(i + 1, current_combination)  # Move to next number
    current_combination.pop()

4. Memory Leak with Global Variables

The Pitfall: Using class-level or global variables that aren't reset between multiple test cases:

class Solution:
    result = []  # Class variable - persists between calls!
  
    def combine(self, n: int, k: int):
        # result still contains data from previous calls
        self.backtrack(1, [], n, k)
        return self.result

The Solution: Always initialize result containers within the method:

class Solution:
    def combine(self, n: int, k: int):
        result = []  # Local variable, fresh for each call
      
        def backtrack(start, current_combination):
            # ... implementation ...
          
        backtrack(1, [])
        return result