本文主要是介绍代码随想录算法训练营第十九天| 回溯理论、77. 组合、216. 组合总和Ⅲ、17. 电话号码的字母组合,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
今日内容
- 回溯的理论基础
- leetcode. 77 组合
- leetcode. 216 组合总和Ⅲ
- leetcode. 17 电话号码的字母组合
回溯理论基础
回溯法也叫回溯搜索法,它是一种搜索的方式,而且只要有递归就会有回溯,回溯就是递归的副产品。
回溯说到底并不是什么非常高深的搜索方式,本质上仍然是穷举,穷举所有可能然后选择出我们要的答案。剪枝会使回溯法更加高效一点,但改变不了回溯本质就是穷举这一事实。
虽然回溯是偏暴力地穷举出所有可能结果,但是这对于某些问题来说已经是很好的解法了,有些问题不求能用多简便的方法求出了,能用暴力法搜索出一个结果就已经是非常不错了。而这些只能用穷举求解的方法可以被概括为下面几类:
- 组合问题:N个数里按一定规则找出K个数的集合
- 切割问题:一个字符串按一定规则有几种切割方式
- 子集问题:一个有N个数的集合里有多少符合条件的子集
- 排列问题:N个数按一定规则全排列,有几种排列方式
- 棋盘问题:N皇后、解数独等
此处比较搞混的是组合问题和排列问题的区别,需要明确:组合不强调元素顺序,而排列强调元素顺序。比如 {1, 2}、{2, 1} 在组合问题中属于同一结果,而在排列问题中就是两个结果。
能用回溯法解决的问题都可以抽象为树形结构,这也是为什么要把回溯法放在二叉树专题后介绍。因为回溯法解决的是在集合中递归查找子集,集合的大小构成了树的宽度,递归深度构成了树的深度。
回溯法一般需要用到回溯函数去解决,而正如之前所说,回溯是递归的副产品,所以回溯函数和递归函数是非常类似的。回溯函数也和递归函数一样拥有三要素:
- 回溯函数返回值和参数。回溯函数的返回值一般为 void,然后回溯函数的参数并不能像做二叉树递归一样一次性确定下来,所以一般写回溯函数是先写逻辑,再写参数。
- 终止条件。一般来说,到叶子节点的时候就可以结束了。
- 单层逻辑。把回溯问题抽象为树形结构后,图片如下。实际上,我们每一层都用一个 for 循环遍历,通过递归下到下一层。这样讲可能会比较抽象,等做了实际题目后,就会比较清晰了。
总体而言,回溯法的解题模板如下所示:
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {处理节点;backtracking(路径,选择列表); // 递归回溯,撤销处理结果}
}
Leetcode. 77 组合
文章链接:代码随想录 (programmercarl.com)
题目链接:77. 组合 - 力扣(LeetCode)
本题从题名看,就知道是组合问题。
借本题也讲讲为什么一定要用递归来进行暴力穷举。一般我们想到的暴力穷举就是使用 for 循环来实现的,像本题中从 n 个数中取 k 个数,如果 k 取值为2、3、4等小数,那么嵌套2、3、4个 for 循环就好。倘若 k 为大数,比如500、1000,嵌套500、1000个 for 循环那就是灾难级别了。
递归就可以避免嵌套多层循环的问题。
前面所说,回溯法能解决的问题都可以抽象为树形结构,该题抽象的树形结构如下图所示:
根据回溯法模板 + 树形结构图,我们写出如下代码:
class Solution {List<List<Integer>> result = new ArrayList<>();List<Integer> elem = new LinkedList<>();public List<List<Integer>> combine(int n, int k) {backtracking(1, n, k);return result;}public void backtracking(int startIndex, int n, int k){if (elem.size() == k){ // 停止条件,当元素长度符合题意时result.add(new ArrayList<>(elem));return;}for (int i = startIndex; i <= n; i++){ // 每一次 for 循环表示当前层的遍历elem.add(i);backtracking(i + 1, n, k); // 递归到下一层elem.remove(elem.size() - 1);}}
}
- 时间复杂度:O(n * 2 ^ n)
- 空间复杂度:O(n)
其中容易搞不明白的就是:
- startIndex
- for 循环与递归的区别
再题目中,我们不希望获取到重复的组合结果,我们希望第一层获取到第一个元素后,递归进入下一层后可以从第二个元素开始遍历。而startIndex的作用就是如此。
再就是 for 循环和递归的区别。for 循环表示当前层的遍历,递归用于进入到下一层。以本题为例,先创建两个列表,一个用于存储临时集合 elem,一个返回最终结果 result:
- 第一层集合为{1, 2, 3, 4},for 循环就是遍历这一层的元素。
- 在遍历到第一个元素时,也就是 1,写入列表 elem。再通过递归进入到第二层。结合 startIndex,第二层的集合就是{2, 3, 4}。
- for 循环遍历第二层的第一个元素,也就是 2,写入列表 elem。此时elem列表长度为 2,符合题意,将结果写入result。进行回溯,将elem的元素 2 剔除。
- for 循环遍历第二层的第二个元素,也就是3,写入列表 elem。此时elem列表长度为 2,符合题意,将结果写入result。进行回溯,将elem的元素 3 剔除。
- for 循环遍历第二层的第三个元素,也就是4,写入列表 elem。此时elem列表长度为 2,符合题意,将结果写入result。进行回溯,将elem的元素 4 剔除。
- 第一层的第一个元素遍历完成,进行第一层第二个元素的遍历。重复步骤3-5,直到第一层集合中的元素被遍历完全。
剪枝操作
虽然回溯本质是穷举,但在某些情况下,穷举已经失去意义,比如我们想要长度为3的集合,但此时剩余元素只有2时,接下来无论如何穷举,剩余元素都无法满足要求。因此剩余无意义的操作就可以通过剪枝剔除,从而提高效率。
剪枝后的代码如下:
class Solution {List<List<Integer>> result = new ArrayList<>();List<Integer> elem = new LinkedList<>();public List<List<Integer>> combine(int n, int k) {backtracking(1, n, k);return result;}public void backtracking(int startIndex, int n, int k){if (elem.size() == k){result.add(new ArrayList<>(elem));return;}// 进行剪枝操作后for (int i = startIndex; i <= n - (k - elem.size()) + 1; i++){elem.add(i);backtracking(i + 1, n, k);elem.remove(elem.size() - 1);}}
}
此处剪枝操作体现在 for 循环的条件表达式上,其中:
- 已经选择的元素个数:elem.size()
- 还需要的元素个数:k - elem.size()
- 在集合中至多要从该起始位置开始遍历:n - ( k - elem.size()) + 1
Leetcode. 216 组合总和Ⅲ
文章链接:代码随想录 (programmercarl.com)
题目链接:216. 组合总和 III - 力扣(LeetCode)
通过上一题的洗礼,对于回溯法的使用有了一些眉目。
题目中有这样一段:该列表不能包含相同的组合两次,为了避免出现同一组合,所以用过的元素都不能再次出现。
将该问题抽象为树形结构,我们可以得到:
根据回溯模板和上述图片,写出如下代码:
class Solution {List<Integer> elem = new LinkedList<>();List<List<Integer>> result = new ArrayList<>();public List<List<Integer>> combinationSum3(int k, int n) {backtracking(1, k, n);return result;}public void backtracking(int startIndex, int k, int n){if (elem.size() == k){int sum = 0;for (int i = 0; i < elem.size(); i++){sum += elem.get(i);}if (sum == n){result.add(new ArrayList<>(elem));return;}}/*此处也可通过剪枝操作提高效率,剪枝后:for (int i = startInex; i <= 9 - (k - elem.size()) + 1; i++)*/for (int i = startIndex; i <= 9; i++){elem.add(i);backtracking(i + 1, k, n);elem.remove(elem.size() - 1);}}
}
- 空间复杂度:O(n * 2 ^ n)
- 时间复杂度:O(n)
Leetcode. 17 电话号码的字母组合
文章链接:代码随想录 (programmercarl.com)
题目链接:17. 电话号码的字母组合 - 力扣(LeetCode)
本题思路:
- 先创建一个映射,可以将数字与对应字母列表映射起来。
- 遍历字符串,读取对应数字的字母列表。
- 分别将这些字母列表的元素进行拼接,做出最后的组合。
代码如下:
class Solution {List<String> result = new ArrayList<>();StringBuilder sb = new StringBuilder();public List<String> letterCombinations(String digits) {if (digits.isEmpty()){return result;}// 创建映射String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};backtracking(digits, map, 0);return result;}public void backtracking(String digits, String[] map, int startIndex){if (digits.length() == startIndex){result.add(sb.toString());return;}// 获取字符串中对应数字的字母列表String list = map[digits.charAt(startIndex) - '0'];// 遍历字母列表for (int i = 0; i < list.length(); i++){sb.append(list.charAt(i));// 递归到字符串中下一个数字的字母列表中backtracking(digits, map, startIndex + 1);sb.deleteCharAt(sb.length() - 1);}}
}
- 时间复杂度:O(3 ^ n * 4 ^ m)
- 空间复杂度:O(3 ^ n * 4 ^ m)
这篇关于代码随想录算法训练营第十九天| 回溯理论、77. 组合、216. 组合总和Ⅲ、17. 电话号码的字母组合的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!