leetcode77--组合

本文主要是介绍leetcode77--组合，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 题意

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

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

2. 题解

1. 回溯+减枝

class Solution {
public:vector<int> temp;vector<vector<int>> ans;void dfs(int cur, int n, int k) {// 剪枝：temp 长度加上区间 [cur, n] 的长度小于 k，不可能构造出长度为 k 的 tempif (temp.size() + (n - cur + 1) < k) {return;}// 记录合法的答案if (temp.size() == k) {ans.push_back(temp);return;}// 考虑选择当前位置temp.push_back(cur);dfs(cur + 1, n, k);temp.pop_back();// 考虑不选择当前位置dfs(cur + 1, n, k);}vector<vector<int>> combine(int n, int k) {dfs(1, n, k);return ans;}
};作者：力扣官方题解
链接：https://leetcode.cn/problems/combinations/solutions/405094/zu-he-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

• 我的

class Solution {
public:void gen(int begin, int n, int k, vector<vector<int>> &ans, vector<int> &seq) {if ( seq.size() == k) {ans.emplace_back(seq);return ;}for (int i = begin; i <= n; ++i) {seq.emplace_back(i);gen(i + 1, n, k, ans, seq);seq.pop_back();}}vector<vector<int>> combine(int n, int k) {vector<vector<int>> ans;vector<int> seq;gen(1, n,k,ans,seq);return ans;}
};

2. 二进制枚举

困难的点在于

• 如何根据字典序顺序生成$k$个1和$n-k$个0的排列
• 如何将二进制的生成排列转换为，序列数的排列

对于问题1，假设当前排列值为$v$,则$next(v)$应为，

1. 若v的最低位为1，从低到高找到最后一个连续的1；将它和它左边的0交换。
   如 n=5,k=3, v=00111 next(v) = 01011
2. 若v的最低位为0，先从低到高过滤掉连续的0, 再找到最高位的连续1, 让它和它左边的0交换；最后再将其低位的1移到最低位。如n=5,k=3; v = 10110, next(v)=11001

我们将1 2对比着看，不难发现情况1实际上是情况2的特殊情况，即没有前面的0要去。

我们可以k位的序列p用1-n来表示第几位上有数字1, 此时的序列也正好对应我们要寻找的答案。
$$len(p)=k,\forall i<k,1\le p_i\le n$$

我们最后做一下转化,连续的1,即对应
$$p[i]+1=p[i+1]$$
而在p表示中，最低位的连续0实际上已经自动去掉了。

• 官解代码

class Solution {
public:vector<int> temp;vector<vector<int>> ans;vector<vector<int>> combine(int n, int k) {// 初始化// 将 temp 中 [0, k - 1] 每个位置 i 设置为 i + 1，即 [0, k - 1] 存 [1, k]// 末尾加一位 n + 1 作为哨兵for (int i = 1; i <= k; ++i) {temp.push_back(i);}temp.push_back(n + 1);int j = 0;while (j < k) {ans.emplace_back(temp.begin(), temp.begin() + k);j = 0;// 寻找第一个 temp[j] + 1 != temp[j + 1] 的位置 t// 我们需要把 [0, t - 1] 区间内的每个位置重置成 [1, t]while (j < k && temp[j] + 1 == temp[j + 1]) {temp[j] = j + 1;++j;}// j 是第一个 temp[j] + 1 != temp[j + 1] 的位置++temp[j];}return ans;}
};作者：力扣官方题解
链接：https://leetcode.cn/problems/combinations/solutions/405094/zu-he-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

这篇关于leetcode77--组合的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---