LeetCode 77 - Combinations

LeetCode Problem 77

Difficulty: 🟡 Medium
Topics: Backtracking

Solution

Problem Understanding

This problem asks us to generate all possible combinations of size k from the numbers in the inclusive range [1, n].

In other words, we are given two integers:

• n, which defines the range of available numbers from 1 to n
• k, which specifies how many numbers each combination must contain

The task is to return every possible way to choose exactly k distinct numbers from this range.

A key detail is that order does not matter. For example, [1,2] and [2,1] represent the same combination and should only appear once. This means we are not generating permutations, where ordering matters, but combinations, where only the selected elements matter.

For example, if n = 4 and k = 2, the available numbers are [1,2,3,4]. We must choose every unique pair of numbers. The valid answers are:

[1,2], [1,3], [1,4], [2,3], [2,4], and [3,4].

The problem guarantees:

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

These constraints are important because the number of combinations can grow quickly. For example:

$$\binom{20}{10} = 184756$$

This means that any valid solution will inherently need to produce many outputs. Since the output itself may be large, an algorithm that generates combinations efficiently without unnecessary repetition becomes important.

The constraints also guarantee that:

• k is never larger than n, so there is always at least one valid combination.
• n is relatively small (<= 20), which makes recursive search techniques practical.
• We never need to handle invalid inputs such as negative numbers or empty ranges.

Some important edge cases to consider include situations where k = 1, k = n, or n is very small. For example, when n = 1 and k = 1, there is only one possible answer: [[1]]. Similarly, when k = n, the only valid combination contains every number from 1 to n.

Approaches

Brute Force Approach

A brute force solution would generate every possible subset of the numbers from 1 to n, then filter out only those subsets whose size equals k.

Since every number can either be included or excluded, there are 2^n possible subsets. For each subset, we would check whether it contains exactly k elements and keep it if it does.

This approach is correct because it explores every possible selection of numbers, guaranteeing that all valid combinations are found. However, it is inefficient because most generated subsets are irrelevant. For example, if k = 2, the brute force method still generates subsets of size 0, 1, 3, and larger.

Because n can be as large as 20, generating all 2^20 = 1,048,576 subsets becomes unnecessarily expensive.

Optimal Approach, Backtracking

The key insight is that we only need to construct valid combinations of size k, rather than generating every possible subset.

Backtracking works well because combinations can be built incrementally. At each step, we choose the next number and recursively continue building the current combination.

To avoid duplicates, we always move forward in ascending order. For example, after choosing 2, we only consider numbers greater than 2. This ensures that [1,2] and [2,1] are never both generated.

The recursive process explores a decision tree:

• Add a number to the current combination
• Recurse to continue building
• Remove the number afterward to explore other possibilities

This technique systematically explores all valid combinations while avoiding unnecessary work.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n × n)	O(2^n × n)	Generates all subsets, then filters by size
Optimal	O(C(n,k) × k)	O(k) excluding output	Builds only valid combinations using backtracking

The optimal approach is significantly better because it only generates the combinations we actually need.

Algorithm Walkthrough

Optimal Algorithm, Backtracking

1. Create an empty result list to store all valid combinations.
2. Create another list called current_combination to keep track of the numbers currently selected.
3. Define a recursive function that takes a start value. This tells us which numbers are still available to choose next.
4. If the length of current_combination equals k, we have completed a valid combination. Add a copy of it to the result list and return immediately.
5. Iterate through all numbers from start to n.
6. Add the current number to current_combination. This represents choosing that number.
7. Recursively call the function with number + 1. This guarantees future selections are larger, preventing duplicates and preserving ascending order.
8. After recursion finishes, remove the last added number. This is the backtracking step, allowing us to explore alternative choices.
9. Continue until all recursive paths have been explored.

Why it works

The algorithm maintains an important invariant: current_combination is always built in strictly increasing order. Because of this, every valid combination is generated exactly once.

Each recursive call represents choosing one additional number, and recursion stops only when exactly k numbers have been selected. Since all valid choices are explored systematically and no duplicate orderings are possible, the algorithm guarantees correctness.

Python Solution

from typing import List

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        result = []
        current_combination = []

        def backtrack(start: int) -> None:
            if len(current_combination) == k:
                result.append(current_combination[:])
                return

            for number in range(start, n + 1):
                current_combination.append(number)
                backtrack(number + 1)
                current_combination.pop()

        backtrack(1)
        return result

The implementation starts by creating two lists: result to store all completed combinations and current_combination to track the combination currently being built.

The nested backtrack function performs the recursive search. It accepts a start parameter, which determines the smallest number that can still be selected. This prevents duplicate combinations and ensures numbers remain in ascending order.

The base case checks whether current_combination has reached size k. If so, a copy of the current list is added to result. A copy is necessary because lists are mutable, and later modifications would otherwise affect stored results.

The loop iterates from start through n. For each candidate number, the algorithm temporarily includes it in the combination, recursively explores further choices, and then removes it afterward. This add, recurse, remove pattern is the essence of backtracking.

Finally, the process begins with backtrack(1), meaning we initially consider all numbers from 1 through n.

Go Solution

func combine(n int, k int) [][]int {
	var result [][]int
	currentCombination := []int{}

	var backtrack func(start int)

	backtrack = func(start int) {
		if len(currentCombination) == k {
			combinationCopy := make([]int, len(currentCombination))
			copy(combinationCopy, currentCombination)
			result = append(result, combinationCopy)
			return
		}

		for number := start; number <= n; number++ {
			currentCombination = append(currentCombination, number)
			backtrack(number + 1)
			currentCombination = currentCombination[:len(currentCombination)-1]
		}
	}

	backtrack(1)
	return result
}

The Go implementation follows the same recursive logic as Python but differs in how slices behave.

Because slices share underlying memory, we must explicitly create a copy before appending a completed combination to result. This is done using make() and copy().

Backtracking is implemented by appending an element to the slice and then removing it with slicing:

currentCombination = currentCombination[:len(currentCombination)-1]

Since n <= 20, integer overflow is not a concern.

Worked Examples

Example 1

Input: n = 4, k = 2

The algorithm starts with:

Step	Current Combination	Start	Action
1	[]	1	Begin recursion
2	[1]	2	Choose 1
3	[1,2]	3	Choose 2, valid combination
4	[1]	2	Backtrack
5	[1,3]	4	Choose 3, valid combination
6	[1]	2	Backtrack
7	[1,4]	5	Choose 4, valid combination
8	[]	1	Backtrack to root
9	[2]	3	Choose 2
10	[2,3]	4	Valid combination
11	[2,4]	5	Valid combination
12	[3]	4	Choose 3
13	[3,4]	5	Valid combination

Final output:

[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

Example 2

Input: n = 1, k = 1

Step	Current Combination	Start	Action
1	[]	1	Begin recursion
2	[1]	2	Valid combination found

Final output:

[[1]]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(C(n,k) × k)	We generate every valid combination, and copying each combination costs O(k)
Space	O(k)	Recursive call stack and temporary combination storage

The time complexity depends on the number of valid combinations, which is:

$$\binom{n}{k}$$

Each completed combination must be copied into the result list, requiring O(k) work.

The auxiliary space complexity is O(k) because recursion depth never exceeds k, and the temporary combination list stores at most k elements at once.

If including the output storage itself, total memory usage becomes:

$$O\left(\binom{n}{k} \times k\right)$$

because all combinations must be stored.

Test Cases

solution = Solution()

# Example cases
assert sorted(solution.combine(4, 2)) == sorted([
    [1, 2], [1, 3], [1, 4],
    [2, 3], [2, 4], [3, 4]
])  # Standard example

assert solution.combine(1, 1) == [[1]]  # Smallest valid input

# Boundary cases
assert solution.combine(2, 2) == [[1, 2]]  # k equals n

assert sorted(solution.combine(5, 1)) == sorted([
    [1], [2], [3], [4], [5]
])  # Single element combinations

assert solution.combine(3, 3) == [[1, 2, 3]]  # Entire range selected

# Additional correctness cases
assert sorted(solution.combine(3, 2)) == sorted([
    [1, 2], [1, 3], [2, 3]
])  # Small combination set

assert sorted(solution.combine(5, 3)) == sorted([
    [1, 2, 3],
    [1, 2, 4],
    [1, 2, 5],
    [1, 3, 4],
    [1, 3, 5],
    [1, 4, 5],
    [2, 3, 4],
    [2, 3, 5],
    [2, 4, 5],
    [3, 4, 5]
])  # Medium-sized case

Test	Why
n=4, k=2	Verifies standard example behavior
n=1, k=1	Tests smallest valid input
n=2, k=2	Validates case where only one combination exists
n=5, k=1	Ensures single-element combinations work correctly
n=3, k=3	Confirms selecting all numbers behaves correctly
n=3, k=2	Verifies smaller recursive branching
n=5, k=3	Tests a larger set of combinations

Edge Cases

Case 1, k = 1

When k = 1, every number from 1 to n becomes its own combination. A buggy implementation might overcomplicate recursion or accidentally produce duplicates.

This implementation handles the case naturally because recursion immediately stops after selecting one number. For example, n = 5, k = 1 produces:

[[1], [2], [3], [4], [5]]

Case 2, k = n

When k equals n, there is only one valid combination containing every number.

A naive implementation could accidentally generate duplicate paths or miss the full combination due to incorrect recursion boundaries. Here, recursion continues selecting numbers in increasing order until all elements are chosen, producing exactly one result.

For example:

n = 4
k = 4

Correct output:

[[1, 2, 3, 4]]

Case 3, Smallest Input Size

The smallest valid input is n = 1, k = 1.

This can expose bugs involving empty loops, incorrect base cases, or recursion initialization. Since the algorithm starts at 1 and immediately reaches size k, it correctly returns:

[[1]]

without requiring any special-case handling.