代码随想录算法训练营第二十四天|leetcode 77. 组合 。-爱代码爱编程
LeetCode 77. 组合
题目链接:LeetCode 77.组合
回溯算法:
class Solution {
private:
vector<int> path;
vector<vector<int>> res;
void backtracking(int n,int k,int startindex)
{
if(path.size() == k)//终止条件为组合大小为目标值k
{
res.push_back(path);//将组合存入结果集中
return;
}
for(int i = startindex;i <= n;i++)//进行for循环
{
path.push_back(i);//存入i
backtracking(n,k,i+1);
path.pop_back();//回溯
}
return;
}
public:
vector<vector<int>> combine(int n, int k) {
backtracking(n,k,1);
return res;
}
};
思路:回溯三部曲:确定参数为n(范围)、k(每个组合大小)、startindex(函数起始位置);终止条件:组合大小为目标大小时,将组合存入结果集中;单层逻辑:通过for循环从1到n进行遍历,存入遍历值i;每次进行下一层递归时,起始位置加一,继续遍历。完成一次组合后进行回溯弹出操作。
剪枝优化:
class Solution {
private:
vector<int> path;
vector<vector<int>> res;
void backtracking(int n,int k,int startline)
{
if(path.size() == k)//终止条件为一维数组大小为目标值k
{
res.push_back(path);//将一维数组存入结果集中
return;
}
for(int i = startline;i <= n-(k - path.size())+1;i++)//剪枝操作
{
path.push_back(i);//存入i
backtracking(n,k,i+1);
path.pop_back();//回溯
}
return;
}
public:
vector<vector<int>> combine(int n, int k) {
backtracking(n,k,1);
return res;
}
};
小结:在一些特殊的组合大小情况下,不需要进行整个树形结构的遍历,通过找到至多遍历点进行剪枝操作可以实现对代码的优化。