dedecms 广告管理 js 网站变慢,网站快速收录技术,东莞建设网雅园新村第20期名单公布,php企业网站多少钱《代码随想录第二十八天》——回溯算法理论基础、组合问题、组合总和III、电话号码的字母组合
本篇文章的所有内容仅基于C撰写。
1. 基础知识
1.1 概念
回溯是递归的副产品#xff0c;它也是遍历树的一种方式#xff0c;其本质是穷举。它并不高效#xff0c;但是比暴力循…《代码随想录第二十八天》——回溯算法理论基础、组合问题、组合总和III、电话号码的字母组合
本篇文章的所有内容仅基于C撰写。
1. 基础知识
1.1 概念
回溯是递归的副产品它也是遍历树的一种方式其本质是穷举。它并不高效但是比暴力循环要快得多在一些没有更高效解法的题目中回溯是很好的方法。例如以下题目
组合问题N个数里面按一定规则找出k个数的集合组合不强调元素顺序排列强调元素顺序。切割问题一个字符串按一定规则有几种切割方式子集问题一个N个数的集合里有多少符合条件的子集排列问题N个数按一定规则全排列有几种排列方式棋盘问题N皇后解数独等等
所有的回溯法都可以抽象为树形结构因为回溯法解决的都是在集合中递归查找子集所以集合的大小就构成了树的宽度递归的深度就构成了树的深度。递归有终止条件所以必然是一棵高度有限的树N叉树。
1.2 模板
回溯函数的返回值与参数 回溯算法中函数返回值一般为void但参数需要根据具体题目确定。回溯函数的终止条件 一般搜索到叶子节点就找到了答案可以结束本次递归。回溯函数的遍历过程 回溯法一般是在集合中递归搜索集合的大小构成了树的宽度递归的深度构成的树的深度。 代码
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果}
}2. 组合
2.1 题目
组合
给定两个整数 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
2.2 分析
这道题中的n和k值如果很大使用for循环嵌套将会造成维数灾难。此时回溯法就发挥了很好的作用。我们使用for循环在当前集合内选一个数作为节点再使用递归法进入下一层以当前节点值之后的所有元素形成新的集合然后再使用for循环选数重复此操作直到一条树枝上的节点数量达到目标值k。 其中回溯操作就是在一个树枝上push_back后再进行pop_back的操作以确保for能在同一个树层上遍历。 注意有个startindex这个值用来确定for循环从哪个值开始遍历并进入递归
2.3 代码
class Solution {
private:vectorvectorint result; // 存放符合条件结果的集合vectorint path; // 用来存放符合条件结果void backtracking(int n, int k, int startIndex) {if (path.size() k) {result.push_back(path);return;}for (int i startIndex; i n; i) {path.push_back(i); // 处理节点backtracking(n, k, i 1); // 递归path.pop_back(); // 回溯撤销处理的节点}}
public:vectorvectorint combine(int n, int k) {result.clear(); // 可以不写path.clear(); // 可以不写backtracking(n, k, 1);return result;}
};时间复杂度: O(n * 2^n)空间复杂度: O(n)
3. 组合III
3.1 题目
组合III
找出所有相加之和为 n 的 k 个数的组合且满足下列条件 只使用数字1到9 每个数字 最多使用一次 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次组合可以以任何顺序返回。
示例 1: 输入: k 3, n 7 输出: [[1,2,4]] 解释: 1 2 4 7 没有其他符合的组合了。
示例 2: 输入: k 3, n 9 输出: [[1,2,6], [1,3,5], [2,3,4]] 解释: 1 2 6 9 1 3 5 9 2 3 4 9 没有其他符合的组合了。
示例 3: 输入: k 4, n 1 输出: [] 解释: 不存在有效的组合。 在[1,9]范围内使用4个不同的数字我们可以得到的最小和是1234 10因为10 1没有有效的组合。
提示: 2 k 9 1 n 60
3.2 分析
节点累加找到相加值为n的树枝时说明找到了一条正确的数枝。因此这道题相对于上一题只是变更了终止条件中的结果记录方式如果元素个数达到目标值k时需要判断当前总值是否与目标值相等相等则将树枝加入结果集再返回不相等则直接return。同样会使用startindex。 另外这道题会涉及到剪枝操作如果当前值已经大于了目标值那么就不需要再继续遍历了。此外for循环的范围也可以剪枝i 9 - (k - path.size()) 1其中
已经选择的元素个数path.size();所需需要的元素个数为: k - path.size();列表中剩余元素n-i 所需需要的元素个数k - path.size()在集合n中至多要从该起始位置 : i n - (k - path.size()) 1开始遍历
这个剪枝方式是横向的因为在该类题的场景下for循环在同层越往后遍历集合越小以至于节点数量可能小于了目标值k这时候就不需要再遍历了这些树枝就可以被剪掉。
3.3 代码
class Solution {
private:vectorvectorint result; // 存放结果集vectorint path; // 符合条件的结果void backtracking(int targetSum, int k, int sum, int startIndex) {if (sum targetSum) { // 剪枝操作return; }if (path.size() k) {if (sum targetSum) result.push_back(path);return; // 如果path.size() k 但sum ! targetSum 直接返回}for (int i startIndex; i 9 - (k - path.size()) 1; i) { // 剪枝sum i; // 处理path.push_back(i); // 处理backtracking(targetSum, k, sum, i 1); // 注意i1调整startIndexsum - i; // 回溯path.pop_back(); // 回溯}}public:vectorvectorint combinationSum3(int k, int n) {result.clear(); // 可以不加path.clear(); // 可以不加backtracking(n, k, 0, 1);return result;}
};时间复杂度: O(n * 2^n)空间复杂度: O(n)
4. 电话号码的字母组合
4.1 题目
电话号码的字母组合
给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。
示例 1 输入digits “23” 输出[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
示例 2 输入digits “” 输出[]
示例 3 输入digits “2” 输出[“a”,“b”,“c”]
提示 0 digits.length 4 digits[i] 是范围 [‘2’, ‘9’] 的一个数字。
4.2 分析
这里的集合不再是数字因此需要考虑映射问题可以使用map或定义一个二维数组来完成映射。其原理与上两题类似只是其中的startindex变为了index其内涵也不相同。index要在给出的数字用例中遍历例如“233”或“4567”。因此终止条件就是遍历完这些数字用例。另外注意考虑边界条件。
4.3 代码
// 版本一
class Solution {
private:const string letterMap[10] {, // 0, // 1abc, // 2def, // 3ghi, // 4jkl, // 5mno, // 6pqrs, // 7tuv, // 8wxyz, // 9};
public:vectorstring result;string s;void backtracking(const string digits, int index) {if (index digits.size()) {result.push_back(s);return;}int digit digits[index] - 0; // 将index指向的数字转为intstring letters letterMap[digit]; // 取数字对应的字符集for (int i 0; i letters.size(); i) {s.push_back(letters[i]); // 处理backtracking(digits, index 1); // 递归注意index1一下层要处理下一个数字了s.pop_back(); // 回溯}}vectorstring letterCombinations(string digits) {s.clear();result.clear();if (digits.size() 0) {return result;}backtracking(digits, 0);return result;}
};时间复杂度: O(3^m * 4^n)其中 m 是对应三个字母的数字个数n 是对应四个字母的数字个数空间复杂度: O(3^m * 4^n)
