#77

Medium

auto_awesomeBacktracking search with pruning

LeetCode Problem Workspace

Combinations

Generate all combinations of k numbers from the range [1, n] using backtracking and pruning.

Problem Statement

Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n]. The combinations should not contain duplicate sets and can be returned in any order. Your task is to implement an algorithm that generates the combinations efficiently using backtracking search with pruning.

You are given that 1 <= n <= 20 and 1 <= k <= n. This problem can be solved using backtracking to explore all possible combinations, but we must prune the search space where invalid or already explored combinations occur to make the process efficient.

Examples

Example 1

Input: n = 4, k = 2

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

There are 4 choose 2 = 6 total combinations. Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.

Example 2

Input: n = 1, k = 1

Output: [[1]]

There is 1 choose 1 = 1 total combination.

Constraints

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

Solution Approach

Backtracking Search

Use backtracking to explore all possible combinations of k numbers from the range [1, n]. At each recursive step, add a number to the current combination and proceed to the next number. Once a valid combination of size k is formed, store it in the result list.

Pruning to Reduce Search Space

Pruning helps reduce unnecessary recursion. When a partial combination exceeds the desired size or becomes invalid, we stop further recursion. This avoids exploring combinations that are impossible or duplicates.

Iterate Over Possible Combinations

Start from the smallest possible number and try all subsequent numbers, building combinations incrementally. When a complete combination is found, backtrack to try other potential combinations.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(C(n, k)), where C(n, k) is the number of combinations of k elements chosen from n. This is because we generate all possible combinations. The space complexity is O(k) due to the storage needed for the current combination at each recursion level.

What Interviewers Usually Probe

The candidate effectively uses backtracking and pruning to reduce redundant searches.
The solution correctly handles the case when n and k are at their boundaries.
The candidate demonstrates a clear understanding of how pruning can optimize backtracking solutions.

Common Pitfalls or Variants

Common pitfalls

Failing to properly backtrack and explore all possible combinations.
Not handling the pruning step correctly, leading to unnecessary recursion and excessive time complexity.
Forgetting to add a valid combination when reaching the desired size k.

Follow-up variants

Generalize the problem by allowing combinations of varying sizes instead of a fixed k.
Implement the solution iteratively instead of recursively for further optimization.
Generate combinations without storing the full set, focusing on the next valid number to explore.

FAQ

How does backtracking work for solving the Combinations problem?

Backtracking explores all possible combinations of k numbers by incrementally building the combination and pruning invalid paths as soon as the solution is invalid.

Why do we need pruning in the Combinations problem?

Pruning avoids unnecessary recursive calls by stopping the exploration of paths that are either too large or impossible, improving efficiency.

What is the time complexity of the Combinations problem?

The time complexity is O(C(n, k)) due to the need to generate all possible combinations of k numbers from n.

How can I optimize my backtracking solution for Combinations?

Use pruning effectively to discard invalid or unnecessary combinations early, reducing the amount of recursion and improving efficiency.

What is the best way to handle the edge case when n = k?

When n equals k, there is only one possible combination: the entire range [1, n], so directly return the result.

terminal

Solution

Solution 1: Backtracking (Two Ways)

We design a function $dfs(i)$, which represents starting the search from number $i$, with the current search path as $t$, and the answer as $ans$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def dfs(i: int):
            if len(t) == k:
                ans.append(t[:])
                return
            if i > n:
                return
            t.append(i)
            dfs(i + 1)
            t.pop()
            dfs(i + 1)

        ans = []
        t = []
        dfs(1)
        return ans

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def dfs(i: int):
            if len(t) == k:
                ans.append(t[:])
                return
            if i > n:
                return
            t.append(i)
            dfs(i + 1)
            t.pop()
            dfs(i + 1)

        ans = []
        t = []
        dfs(1)
        return ans

Continue Practicing

#78 subsets #79 word search #89 gray code