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.

#77

Medium

auto_awesome回溯·pruning

LeetCode 题解工作台

组合

给定两个整数 n 和 k ，返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按任何顺序返回答案。示例 1：输入： n = 4, k = 2 输出： [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] 示例 2：输入： n = 1, k …

回溯

题目描述

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

提示：

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

lightbulb

解题思路

方法一：回溯（两种方式）

我们设计一个函数 $dfs(i)$ ，表示从数字 $i$ 开始搜索，当前搜索路径为 $t$ ，答案为 $ans$ 。

函数 $dfs(i)$ 的执行逻辑如下：

如果当前搜索路径 $t$ 的长度等于 $k$ ，则将当前搜索路径加入答案，然后返回。
如果 $i \gt n$ ，则说明搜索已经结束，返回。
否则，我们可以选择将数字 $i$ 加入搜索路径 $t$ ，然后继续搜索，即执行 $dfs(i + 1)$ ，然后将数字 $i$ 从搜索路径 $t$ 中移除；或者不将数字 $i$ 加入搜索路径 $t$ ，直接执行 $dfs(i + 1)$ 。

以上做法实际上是枚举当前数字选或者不选，然后递归地搜索下一个数字。我们也可以枚举下一个要选择的数字 $j$ ，其中 $i \leq j \leq n$ ，如果下一个要选择的数字是 $j$ ，那么我们将数字 $j$ 加入搜索路径 $t$ ，然后继续搜索，即执行 $dfs(j + 1)$ ，接着将数字 $j$ 从搜索路径 $t$ 中移除。

在主函数中，我们从数字 $1$ 开始搜索，即执行 $dfs(1)$ 。

时间复杂度 $(C_n^k \times k)$ ，空间复杂度 $O(k)$ 。其中 $C_n^k$ 表示组合数。

相似题目：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

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

speed

复杂度分析

指标	值
时间	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.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#78 子集 #79 单词搜索 #89 格雷编码