Combinations

TIP103 Unit 8 Session 2 (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 25-30 mins
• 🛠️ Topics: Recursion, Backtracking, Combinations

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• Q: What exactly are we being asked to return?

  • A: A list of all possible combinations of k distinct numbers chosen from the range [1, n], where each combination is itself a list.

• Q: Does the order of numbers within a combination matter?

  • A: No. Order within a combination does not matter, so [1, 2] and [2, 1] are the same ticket and should only appear once. We can avoid duplicates by always building combinations in increasing order.

• Q: Can a number be repeated within a single combination?

  • A: No. Each combination consists of k distinct numbers from 1 to n.

HAPPY CASE
Input: n = 4, k = 2
Output: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
Explanation: There are 6 ways to choose 2 distinct numbers from [1, 4]. Note that [2, 1] does not appear because it is the same combination as [1, 2].

EDGE CASE
Input: n = 1, k = 1
Output: [[1]]
Explanation: There is only one number to choose from, so the only possible ticket is [1].

Input: n = 3, k = 3
Output: [[1, 2, 3]]
Explanation: When k equals n, every number must be picked, so there is exactly one combination.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Generating All Combinations, we can consider the following approaches:

• Backtracking: Build each combination one number at a time; when a partial combination cannot grow into a valid one (or is complete), backtrack and try the next candidate. This is the standard pattern for "generate all X" problems.
• Recursion (Include/Exclude): For each number, recursively decide to either include it in the current combination or skip it.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Use backtracking to build combinations in increasing order. Maintain a current partial combination and a start value marking the smallest number still allowed. At each step, try every candidate from start to n: add it, recurse with start set just past it, then remove it and try the next candidate. Because we only ever move forward through the range, each combination is generated exactly once and duplicates like [2, 1] never occur. When current reaches length k, record a copy of it.

1) Initialize an empty list `combinations` to collect results.
2) Define a helper function backtrack(start, current):
   a) Base case: if len(current) == k, append a copy of `current` to `combinations` and return.
   b) For each number `num` from `start` to `n`:
      i)   Append `num` to `current` (choose).
      ii)  Recurse with backtrack(num + 1, current) (explore).
      iii) Pop `num` from `current` (un-choose / backtrack).
3) Call backtrack(1, []).
4) Return `combinations`.

⚠️ Common Mistakes

• Appending current itself instead of a copy (current[:]), so later backtracking mutates results already stored in the answer.
• Recursing with start + 1 instead of num + 1, which produces duplicate combinations and combinations with repeated numbers.
• Forgetting to pop the last number after the recursive call, so the partial combination keeps growing incorrectly.
• Iterating candidates from 1 every time instead of from start, generating reorderings like [2, 1] alongside [1, 2].

4: I-mplement

Implement the code to solve the algorithm.

def combine(n, k):
    combinations = []

    def backtrack(start, current):
        # Base case: the current combination is complete
        if len(current) == k:
            combinations.append(current[:])  # Append a copy
            return
        # Try each remaining candidate number in increasing order
        for num in range(start, n + 1):
            current.append(num)          # Choose
            backtrack(num + 1, current)  # Explore
            current.pop()                # Un-choose (backtrack)

    backtrack(1, [])
    return combinations

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Input: n = 4, k = 2

  • backtrack(1, []) tries 1: current = [1], then extends with 2, 3, 4 → records [1, 2], [1, 3], [1, 4].
  • Backtrack to [], try 2: current = [2], extends with 3, 4 → records [2, 3], [2, 4].
  • Backtrack, try 3: current = [3], extends with 4 → records [3, 4].
  • Try 4: current = [4] cannot reach length 2 (no candidates left), nothing recorded.
  • Output: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]] ✅ matches the example.

• Input: n = 1, k = 1

  • backtrack(1, []) tries 1: current = [1] hits length 1 → records [1].
  • Output: [[1]]

• Input: n = 3, k = 3

  • The only path that reaches length 3 is 1 → 2 → 3.
  • Output: [[1, 2, 3]]

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the value of n (the size of the number range) and K is the value of k (the size of each combination).

• Time Complexity: O(C(N, K) * K) — there are C(N, K) ("N choose K") combinations in the output, and each one costs O(K) to copy into the results list.
• Space Complexity: O(K) auxiliary space for the recursion stack and the current partial combination (the output itself takes O(C(N, K) * K) space, which is required by the problem).