leetcode77：组合

给定两个整数 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：问题分析

问题定义

给定两个整数 nn 和 kk，要求找出从范围 [1,n][1, n] 中选择的所有 kk 个数的组合。
输出为二维数组，其中每个子数组表示一种组合，且无需按特定顺序。

输入条件

1≤n≤201 \leq n \leq 20：表示可以选择的数的范围为 [1,n][1, n]。
1≤k≤n1 \leq k \leq n：表示从 nn 个数中选择的元素个数。

输出条件

返回所有可能的 kk 元组合，顺序任意。

边界条件

如果 k=1k = 1，则每个元素独立成组，例如 n=4n = 4 时输出 [[1],[2],[3],[4]][[1], [2], [3], [4]]。
如果 k=nk = n，则输出所有元素的唯一组合，例如 n=4n = 4 时输出 [[1,2,3,4]][[1, 2, 3, 4]]。
如果 k>nk > n，按照问题定义不可能出现这种情况，因此无需处理此特殊情形。

步骤 2：算法设计与分析

解法思路

这是一个典型的组合问题，核心是生成所有满足条件的组合，可以通过以下两种方式实现：

递归回溯法（Backtracking）
- 回溯法是解决组合和排列问题的经典方法。
- 核心思想是通过递归枚举每个数是否加入当前组合，逐步生成所有合法的组合。
- 关键点：
  - 在递归函数中维护一个当前的组合。
  - 在每一层中尝试将下一个可能的数加入组合，并在完成组合后回退到上一层。
- 时间复杂度：O(C(n,k))O(C(n, k))，即组合数 (nk)\binom{n}{k}。
- 空间复杂度：O(k)O(k)，递归栈的深度取决于 kk。
迭代法（非递归）
- 利用字典序生成组合（类似于二进制选择法）。
- 需要手动实现一个状态更新的过程，复杂性较高，但可避免递归。

对于本问题，优先采用 递归回溯法，其逻辑清晰且实现相对简单。

步骤 3： C++ 实现

// 回溯法生成组合
class Solution {
public:vector<vector<int>> combine(int n, int k) {vector<vector<int>> result; // 用于存储最终的结果vector<int> current;       // 用于存储当前的组合backtrack(1, n, k, current, result); // 从数字1开始搜索return result;}private:// 回溯函数void backtrack(int start, int n, int k, vector<int>& current, vector<vector<int>>& result) {// 递归终止条件：如果当前组合长度达到k，保存组合if (current.size() == k) {result.push_back(current);return;}// 从start开始枚举每个可能的数for (int i = start; i <= n; i++) {current.push_back(i);         // 将数字i加入当前组合backtrack(i + 1, n, k, current, result); // 递归处理下一个数字current.pop_back();           // 回溯，移除最后加入的数字}}
};

代码运行示例

输入：n=4,k=2n = 4, k = 2
输出：

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

步骤 4：解题启发

回溯法的强大能力
- 回溯法不仅可以解决组合问题，还可以处理排列、子集等问题，通过适当修改递归逻辑，可以灵活应对多种需求。
- 深刻理解递归的退出条件和选择路径，是掌握回溯法的关键。
算法优化空间
- 本题可以通过剪枝优化，例如提前判断当前路径是否还有足够的元素可用，从而减少无意义的递归调用。