目录

力扣77. 组合

解析代码

---

力扣77. 组合

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

class Solution {
public:vector<vector<int>> combine(int n, int k) {}
};

---

解析代码

        题目要求我们从 1 到 n 中选择 k 个数的所有组合，其中不考虑顺序。也就是说，[1,2] 和 [2,1] 等价。我们需要找出所有的组合，但不能重复计算相同元素的不同顺序的组合。对于选择组合，我们需要进行如下流程：

1. 所有元素分别作为首位元素进行处理。
2. 在之后的位置上同理，选择所有元素分别作为当前位置元素进行处理。
3. 为避免计算重复组合，规定选择之后位置的元素时必须比前一个元素大，这样就不会有重复的组合 （[1,2] 和 [2,1] 中 [2,1] 不会出现）。

class Solution {int _n, _k;vector<int> path;vector<vector<int>> ret;
public:vector<vector<int>> combine(int n, int k) {_n = n;_k = k;dfs(1);return ret;}void dfs(int pos){if(path.size() == _k){ret.push_back(path);return;}for(int i = pos; i <= _n; ++i) // 剪枝{path.push_back(i);dfs(i + 1);path.pop_back(); // 恢复现场}}
};