回溯模板
2023-02-18 16:41:52 时间
回溯模板
//交换版
void backtrack(int index, vector<int> &s){
if(/*满足的条件*/){
/*加入结果*/
return;
}
for(int i=index;i<s.size();i++){
swap(s[i], s[index]);
backtrack(index+1, s);
swap(s[i], s[index]);
}
}
//添加删除版
void backtrack(vector<int> &s, vector<int> &temp/*或者是string*/){
if(/*满足的条件*/){
/*加入结果*/
return;
}
for(int i=index;i<s.size();i++){
temp.push_back(s[i]);
backtrack(s, temp);
temp.pop_back();
}
}
下面是上面两个模板的实例,两个方法通用
```c++
//全排列II https://leetcode-cn.com/submissions/detail/163570148/
class Solution {
public:
set<vector<int>> res;
vector<vector<int>> permuteUnique(vector<int>& nums) {
backtrace(0,nums.size()-1, nums);
return vector<vector<int>>(res.begin(), res.end());
}
void backtrace(int index, int n, vector<int>& nums){
if(index==n){
res.insert(nums);
return;
}
for(int i=index;i<=n;i++){
swap(nums[i], nums[index]);
backtrace(index+1, n, nums);
swap(nums[i], nums[index]);
}
}
};
//全排列 https://leetcode-cn.com/problems/permutations/
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
vector<int> ans;
backtrace(nums, res, ans);
return res;
}
void backtrace(vector<int>& nums, vector<vector<int>>& res, vector<int>& ans)
{
/*满足结束条件*/
if(ans.size()==nums.size()){
res.push_back(ans);
return ;
}
for(vector<int>::iterator it=nums.begin(); it != nums.end(); it++)
{
int x = *it;
if(find(ans.begin(),ans.end(),x) != ans.end())//x在路径中,不考虑
{
continue;
}
ans.push_back(x);//选择x
backtrace(nums, res, ans);//下一步
ans.erase( ans.end()-1, ans.end() );//撤销选择
}
return ;
}
};
当然对于树或者图的,遍历循环改成左右子树就可,下面是257.二叉树的所有路径
链接:https://leetcode-cn.com/problems/binary-tree-paths/solution/yi-pian-wen-zhang-jie-jue-suo-you-er-cha-5f58/
vector<string> res;
vector<string> binaryTreePaths(TreeNode<T> *root)
{
dfs(root, "");
return res;
}
void dfs(TreeNode*root, string path)
{
if (!root)
return;
path += to_string(root->val);
if (!root->left && !root->right)
{
res.push_back(path);
return;
}
dfs(root->left, path+"->");
dfs(root->right, path+"->");
}
相关文章
- 抓 https 加密数据,偷偷摸摸爽得很!
- 小游戏赛道迎来新一轮增长机会,技术升级实现多平台布局
- Photoshop 2021正式版更新,附全系列下载
- Ps | Adobe Photoshop 2023 for Win 24.1 中文激活版下载及安装教程
- 简单易用的监控告警系统 | HertzBeat 在 Rainbond 上的使用分享
- 原来Docker容器中设置时区这么简单
- 小游戏进入增长快车道,行业变现模式分析
- (一)汇编语言——基础知识
- ghost系统后只有C盘了别的盘的文件怎样恢复
- (二)汇编语言——寄存器
- (三)汇编语言——DOSBox
- 分布式是大数据处理的万能药?
- SAP ABAP 报表屏幕输入字段如何实现联动效果试读版
- 如何给 SAP ABAP ALV 报表的修改功能添加自定义校验逻辑试读版
- 参加 Spartacus 开源项目开发时需要注意的一些编程规范
- Salesforce LWC学习(四十) datatable的dynamic action的小坑浅谈
- 内科大软件工程导论复习内容笔记
- Prometheus及Grafana监控服务的安装使用
- SpringBoot:模块探究之spring-boot-cli
- java中的lambda表达式(从小白也能看懂做起)