LeetCode 77: Combinations Solution in Python Explained

Problem Statement

LeetCode 77, Combinations, is a medium-level problem where you’re given two integers n and k. Your task is to return all possible combinations of (k) numbers out of the range ([1, n]), in any order. Each combination is a list of (k) distinct integers from 1 to (n), and the result is a list of all such combinations.

Constraints

1 <= n <= 20: Range of numbers is between 1 and 20.
1 <= k <= n: Size of combinations is between 1 and \(n\).

Example

Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: All pairs from 1 to 4: 6 combinations.

Input: n = 1, k = 1
Output: [[1]]
Explanation: Only one combination of size 1 from [1].

Input: n = 3, k = 3
Output: [[1,2,3]]
Explanation: Only one combination of size 3 from [1,2,3].

Understanding the Problem

How do you solve LeetCode 77: Combinations in Python? For n = 4, k = 2, generate all possible pairs from [1,2,3,4], resulting in [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]. We need to select (k) numbers from (n) options, ensuring each combination is unique. We’ll explore two approaches: a Backtracking Solution (optimal and primary) and an Alternative with Iterative Approach (systematic but less common). The backtracking method runs in O(C(n,k)) time with O(k) space for the recursion stack, where (C(n,k)) is the binomial coefficient.

Solution 1: Backtracking Approach (Primary)

Explanation

Use backtracking to build combinations by adding numbers one at a time, exploring all possibilities. Start with an empty combination, add numbers from 1 to (n), and backtrack when the combination reaches size (k) or when no more valid numbers can be added. Prune branches by only considering numbers greater than the last added to avoid duplicates.

Here’s a flow for (n = 4, k = 2):

Start: []
Add 1: [1] -> [1,2], [1,3], [1,4]
Add 2: [2] -> [2,3], [2,4]
Add 3: [3] -> [3,4]
Result: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

Initialize Result.

List to store combinations.

Backtrack.

Build combination, add when size = \(k\).

Prune Search.

Start from last number + 1 to avoid repeats.

Return Result.

Step-by-Step Example

Example 1: n = 4, k = 2

We need [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]].

Goal: Generate all combinations of 2 numbers from 1 to 4.
Result for Reference: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]].
Start: n = 4, k = 2, result = [], curr = [], start = 1.
Step 1: start = 1.

Add 1, curr = [1].
start = 2, add 2, curr = [1,2], size = 2, result = [[1,2]].
Backtrack, curr = [1], add 3, curr = [1,3], result = [[1,2],[1,3]].
Backtrack, curr = [1], add 4, curr = [1,4], result = [[1,2],[1,3],[1,4]].

Step 2: Backtrack, curr = [], start = 2.

Add 2, curr = [2].
start = 3, add 3, curr = [2,3], result = [[1,2],[1,3],[1,4],[2,3]].
Backtrack, curr = [2], add 4, curr = [2,4], result = [[1,2],[1,3],[1,4],[2,3],[2,4]].

Step 3: Backtrack, curr = [], start = 3.

Add 3, curr = [3].
start = 4, add 4, curr = [3,4], result = [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]].

Finish: Return [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]].

Example 2: n = 1, k = 1

We need [[1]].

Start: curr = [], start = 1.
Step 1: Add 1, curr = [1], size = 1, result = [[1]].
Finish: Return [[1]].

How the Code Works (Backtracking)

Here’s the Python code with line-by-line explanation:

def combine(n: int, k: int) -> list[list[int]]:
    # Line 1: Initialize result
    result = []

    # Line 2: Backtracking helper
    def backtrack(curr: list[int], start: int) -> None:
        # Line 3: Base case: combination complete
        if len(curr) == k:
            result.append(curr[:])
            return

        # Line 4: Explore numbers from start to n
        for i in range(start, n + 1):
            curr.append(i)
            backtrack(curr, i + 1)
            curr.pop()

    # Line 5: Start backtracking
    backtrack([], 1)

    # Line 6: Return all combinations
    return result

Alternative: Iterative Approach

Explanation

Generate combinations iteratively by maintaining a list of current combinations and extending them with new numbers until size (k) is reached. Start with single numbers, then build up, ensuring lexicographical order.

Initialize Combinations.

Start with [1], [2], ..., [n].

Extend Combinations.

Add numbers iteratively up to size \(k\).

Return Result.

Step-by-Step Example (Alternative)

For (n = 4, k = 2):

Start: combos = [[1], [2], [3], [4]].
Step 1: Extend to size 2.

[1] -> [1,2], [1,3], [1,4].
[2] -> [2,3], [2,4].
[3] -> [3,4].

Finish: combos = [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]].

How the Code Works (Iterative)

def combineIter(n: int, k: int) -> list[list[int]]:
    # Line 1: Initialize with single numbers
    result = [[i] for i in range(1, n + 1)]

    # Line 2: Extend combinations to size k
    for _ in range(k - 1):
        new_result = []
        for combo in result:
            start = combo[-1] + 1
            for i in range(start, n + 1):
                new_result.append(combo + [i])
        result = new_result

    # Line 3: Return all combinations
    return result

Complexity

Backtracking:

Time: O(C(n,k)) – Number of combinations generated.
Space: O(k) – Recursion stack depth.

Iterative:

Time: O(C(n,k)) – Generate all combinations iteratively.
Space: O(C(n,k)) – Store all combinations at each step.

Efficiency Notes

Backtracking is O(C(n,k)) time and O(k) space, optimal for LeetCode 77 as it generates combinations on-the-fly with minimal extra space. Iterative is O(C(n,k)) time and O(C(n,k)) space, less efficient in space but straightforward, storing intermediate results.

Key Insights

Tips to master LeetCode 77:

Backtracking: Build combinations recursively.
Pruning: Use start index to avoid duplicates.
Combination Count: \(C(n,k) = n! / (k! * (n-k)!)\).

Additional Example

For (n = 3, k = 2):

Goal: [[1,2],[1,3],[2,3]].
Backtracking: [1,2], [1,3], [2,3], return [[1,2],[1,3],[2,3]].
Result: [[1,2],[1,3],[2,3]].

Edge Cases

\(n = k\): n=3, k=3 – Return [[1,2,3]].
\(k = 1\): n=3, k=1 – Return [[1],[2],[3]].
\(n = 1\): n=1, k=1 – Return [[1]].

Final Thoughts

The Backtracking solution is a top choice for LeetCode 77 in Python—flexible, efficient, and recursive, with the Iterative approach offering a systematic alternative. For a related challenge, try LeetCode 76: Minimum Window Substring to switch to strings! Ready to combine? Solve LeetCode 77 on LeetCode now and test it with (n=4, k=2) or (n=3, k=2) to master combinations. Dive in and pick your numbers!