算法与数据结构基础 - 回溯(Backtracking)
2024-09-01 05:12:33
回溯基础
先看一个使用回溯方法求集合子集的例子(78. Subsets),以下代码基本说明了回溯使用的基本框架:
//78. Subsets class Solution { private: void backtrack(vector<vector<int>>& res,vector<int>& tmp,vector<int>& nums,int start){ res.push_back(tmp); //满足一定条件下将当前数据加入结果集 for(int i=start;i<nums.size();i++){ tmp.push_back(nums[i]); //选择一条路径 backtrack(res,tmp,nums,i+); //DFS朝当前路径行进 tmp.pop_back(); //回退路径 } } public: vector<vector<int>> subsets(vector<int>& nums) { vector<vector<int>> res; vector<int> tmp; backtrack(res,tmp,nums,); return res; } };
即回溯方法主要有以下四个步骤:
. 满足一定条件下将当前数据加入结果集 (或检查到不满足要求当即返回) . 选择一条路径 . DFS向前进行 . 回退路径
一些情况下需要对数据进行预先处理,或在第2步直接检查以决定是否抛弃当前路径,以避免过多地递归、带来时间损耗。换而言之,不满足条件的路径越早抛弃越好。
理解回溯
回溯方法用到递归,涉及到递归让我们理解起来就不那么直观。下图直观展示了以上Subsets求解代码的执行过程,第5步开始出现路径回退:
可以把回溯的执行理解为一颗树从根到叶、从左到右的展开过程。图片来源 这里
回溯时间复杂度
同样因为用到递归,时间复杂度亦不能够直观地计算,以上Subsets问题比较容易地能看出来为O(2^n)。如果对递归过程计算时间复杂度,详见 这里
相关LeetCode题:
最新文章
- Access restriction: The type &#39;FileURLConnection&#39; is not API
- Top 10 Methods for Java Arrays
- sublimetext2 中运行Python提示EOFError: EOF when reading a line
- U盘安装Win7 64位
- gdb 技巧
- CentOS7使用Redis
- JS 返回上一步(退回上一步上一个网页)
- Coreseek:常见的问题2
- 一步一步学c#(五):泛型
- [模版]平衡树splay2
- C程序练习
- 《剑指Offer》第20题(Java实现):定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。
- MySql 5.7.20版本免安装版配置过程
- 纯CSS打造萌萌哒大白
- Flex 确定弹出窗口的绝对位置x , y
- 未能加载文件或程序集&ldquo;Microsoft.SqlServer.Management.Sdk.Sfc, Version=11.0.0.0, Culture=neutral, PublicKeyToken=89845dcd8080cc91&rdquo;或它的某一个依赖项。系统找不到指定的文件。
- e826. 获得和设置JSplitPane分开的位置
- jenkins -Djava.awt.headless=true Linux下java.awt.HeadlessException的解决办法
- Android PackageManager:queryIntentActivities
- PTA (Advanced Level) 1015 Reversible Primes
热门文章
- jieba GitHUb 结巴分词
- kuangbin专题 专题一 简单搜索 Dungeon Master POJ - 2251
- 嵊州D4T1 翻车 rollover 真的翻车了
- 学习使用Quartz,java
- 【基础算法-模拟-例题-玩具谜题】-C++
- python如何将一个多位数数值转换为列表类型
- xx.exe 中的 0x014180bd 处有未经处理的异常: 0xC0000005: 读取位置 0xfeeefeee 时发生访问冲突(当指针访问异常时,应考虑是不是对象未创建)。
- C#3.0新增功能10 表达式树 01 简介
- [小米OJ] 3. 大数相减
- org.mybatis.spring.MyBatisSystemException异常及处理