零、原题链接

77. 组合

一、题目描述

给定两个整数 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

三、解题思路

1. 基本思路：
     回溯+剪枝，对于每个元素，我们可以选或者不选，如果太多次不选，可能无法构成指定长度的组合，则可以提前剪枝。
2. 具体思路：
   • 编写 dfs 函数
     • 如果确定了 k 个元素，则记录答案
     • 如果剩下的元素不足以构成长度为 k 的组合，则提前结束【剪枝】
     • 选择这个元素，递归调用确定下一个元素的选取
     • 不选这个元素，递归调用确定下一个元素的选取
   • 调用 dfs 函数，返回结果

四、参考代码

时间复杂度：$\mathrm{O}(C_n^k)$
空间复杂度：$\mathrm{O}(n)$

class Solution {
public:int _k;vector<vector<int>> ans;vector<int> t;void dfs(const int& n) {if (t.size() == _k) {ans.emplace_back(t);return;}if (n < _k - t.size()) // 提前剪枝return;t.emplace_back(n);dfs(n - 1);t.pop_back();dfs(n - 1);}vector<vector<int>> combine(int n, int k) {_k = k;dfs(n);return ans;}
};