77. Combinations - Explanation

Description

You are 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 = 3, k = 2

Output: [
    [1,2],
    [1,3],
    [2,3]
]

Example 2:

Input: n = 3, k = 3

Output: [[1,2,3]]

Constraints:

1 <= k <= n <= 20

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Backtracking - I

Intuition

To generate all combinations of k numbers from 1 to n, we make a binary choice for each number: include it or exclude it. This forms a decision tree where each path represents a subset. We only keep subsets of exactly size k.

Algorithm

Start with an empty combination and index i = 1.
At each step, we have two choices: include the current number i in the combination, or skip it.
Recursively process both choices by incrementing i.
When i exceeds n, check if the combination has exactly k elements. If so, add a copy to the result.
Backtrack by removing the added element before exploring the skip branch.

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

        def backtrack(i, comb):
            if i > n:
                if len(comb) == k:
                    res.append(comb.copy())
                return

            comb.append(i)
            backtrack(i + 1, comb)
            comb.pop()
            backtrack(i + 1, comb)

        backtrack(1, [])
        return res

Time & Space Complexity

Time complexity: $O(k * \frac {n!}{(n - k)! * k!})$
Space complexity: $O(k * \frac {n!}{(n - k)! * k!})$ for the output array.

Where $n$ is the number of elements and $k$ is the number of elements to be picked.

2. Backtracking - II

Intuition

Instead of making include/exclude decisions, we iterate through available numbers and always include one. Starting from a given position ensures we never revisit smaller numbers, avoiding duplicates. We stop when the combination reaches size k.

Algorithm

Start with an empty combination and a starting index of 1.
If the combination size equals k, save a copy to the result and return.
Iterate from the start index to n. For each number, add it to the combination.
Recursively call with start = i + 1 to only consider larger numbers.
Remove the last element (backtrack) before trying the next number.

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

        def backtrack(start, comb):
            if len(comb) == k:
                res.append(comb.copy())
                return

            for i in range(start, n + 1):
                comb.append(i)
                backtrack(i + 1, comb)
                comb.pop()

        backtrack(1, [])
        return res

Time & Space Complexity

Time complexity: $O(k * \frac {n!}{(n - k)! * k!})$
Space complexity: $O(k * \frac {n!}{(n - k)! * k!})$ for the output array.

Where $n$ is the number of elements and $k$ is the number of elements to be picked.

3. Iteration

Intuition

We can simulate backtracking iteratively using an array of size k to track our current combination. An index pointer moves forward when we find valid numbers and backward when we need to backtrack. This eliminates recursion overhead.

Algorithm

Initialize an array of size k with zeros and a pointer i = 0.
Increment comb[i] to try the next value at position i.
If comb[i] exceeds n, move the pointer back (i -= 1) to backtrack.
If i reaches k - 1, we have a complete combination; save it.
Otherwise, move forward (i += 1) and set comb[i] = comb[i - 1] so the next position starts just after the previous value.
Repeat until i becomes negative.

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
        i = 0
        comb = [0] * k

        while i >= 0:
            comb[i] += 1
            if comb[i] > n:
                i -= 1
                continue

            if i == k - 1:
                res.append(comb.copy())
            else:
                i += 1
                comb[i] = comb[i - 1]

        return res

Time & Space Complexity

Time complexity: $O(k * \frac {n!}{(n - k)! * k!})$
Space complexity: $O(k * \frac {n!}{(n - k)! * k!})$ for the output array.

Where $n$ is the number of elements and $k$ is the number of elements to be picked.

4. Bit Manipulation

Intuition

Each subset of numbers from 1 to n can be represented as an n-bit binary number, where bit i being set means number (i+1) is included. We iterate through all possible bitmasks and keep only those with exactly k bits set.

Algorithm

Iterate through all integers from 0 to 2^n - 1. Each integer represents a possible subset.
For each mask, extract the numbers corresponding to set bits (if bit j is set, include j + 1).
If the resulting subset has exactly k elements, add it to the result.
Return all valid combinations.

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
        for mask in range(1 << n):
            comb = []
            for bit in range(n):
                if mask & (1 << bit):
                    comb.append(bit + 1)

            if len(comb) == k:
                res.append(comb)
        return res

Time & Space Complexity

Time complexity: $O(n * 2 ^ n)$
Space complexity: $O(k * \frac {n!}{(n - k)! * k!})$ for the output array.

Where $n$ is the number of elements and $k$ is the number of elements to be picked.

Common Pitfalls

Forgetting to Copy the Combination Before Adding to Results

When adding the current combination to the result list, you must create a copy. Otherwise, subsequent modifications during backtracking will alter the already-added result.

# Wrong: adds reference that gets modified
res.append(comb)

# Correct: adds a copy
res.append(comb.copy())

Missing the Backtrack Step

After exploring a branch with an element included, you must remove it before exploring the next branch. Forgetting to pop leads to combinations with too many elements.

comb.append(i)
backtrack(i + 1, comb)
# Missing: comb.pop()

Using Wrong Loop Bounds

Starting the loop at 0 instead of start causes duplicate combinations like [1,2] and [2,1]. The loop must start from the current position to ensure each combination is generated only once in sorted order.