首页 > 编程语言 >代码随想录算法训练营第二十四天 | 第七章 回溯算法-理论基础,77. 组合

代码随想录算法训练营第二十四天 | 第七章 回溯算法-理论基础,77. 组合

时间:2023-02-07 22:01:34浏览次数:59  
标签:int res 随想录 back 77 算法 vector path backtracking

一、参考资料

理论基础

题目链接/文章讲解:https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E7%AE%97%E6%B3%95%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

视频讲解:https://www.bilibili.com/video/BV1cy4y167mM

组合

题目链接/文章讲解:https://programmercarl.com/0077.%E7%BB%84%E5%90%88.html

视频讲解:https://www.bilibili.com/video/BV1ti4y1L7cv

剪枝操作:https://www.bilibili.com/video/BV1wi4y157er

二、理论基础

回溯的遍历过程如图:

三、LeetCode77. 组合

https://leetcode.cn/problems/combinations/description/

组合问题抽象

给定两个整数 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
  1. class Solution {
  2. private:
  3. vector<vector<int>> res; // 定义一个结果集数组
  4. vector<int> path; // 定义路径,用来存放符合条件的结果
  5. void backtracking (int n, int k, int startIndex) {
  6. if (path.size() == k) {
  7. res.push_back(path);
  8. return ;
  9. }
  10. for (int i = startIndex; i <= n; i++) {
  11. path.push_back(i); // 处理节点
  12. backtracking(n, k, i + 1); // 递归
  13. path.pop_back(); // 回溯,撤销处理的节点
  14. }
  15. }
  16. public:
  17. vector<vector<int>> combine(int n, int k) {
  18. backtracking(n, k, 1);
  19. return res;
  20. }
  21. };

我写的:

  1. class Solution {
  2. private:
  3. vector<int> path; // 用于存放符合条件的路径
  4. vector<vector<int>> res; // 用于存放结果集
  5. void backtracking(int n, int k, int startIndex) {
  6. // startIndex是为了防止重复组合(排列才和元素顺序有关)
  7. if (path.size() == k) {
  8. res.push_back(path);
  9. return ;
  10. }
  11. for (int i = startIndex; i <= n; i++) {
  12. path.push_back(i);
  13. backtracking(n, k, i + 1);
  14. path.pop_back();
  15. }
  16. }
  17. public:
  18. vector<vector<int>> combine(int n, int k) {
  19. backtracking(n, k, 1);
  20. return res;
  21. }
  22. };

剪枝操作:【看了两三遍,这个剪枝的条件有点点绕的】

图中每一个节点(图中为矩形),就代表本层的一个for循环,那么每一层的for循环从第二个数开始遍历的话,都没有意义,都是无效遍历。

所以,可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。

如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了,那么就没有必要搜索了。

注意代码中i,就是for循环里选择的起始位置。

for (int i = startIndex; i <= n; i++) {

接下来看一下优化过程如下:

  1. 已经选择的元素个数:path.size();

  1. 还需要的元素个数为: k - path.size();

  1. 在集合n中至多要从该起始位置 : n - (k - path.size()) + 1,开始遍历

为什么有个+1呢,因为包括起始位置,我们要是一个左闭的集合。

举个例子,n = 4,k = 3, 目前已经选取的元素为0(path.size为0),n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。

从2开始搜索都是合理的,可以是组合[2, 3, 4]。

  1. class Solution {
  2. // 剪枝
  3. private:
  4. vector<vector<int>> res;
  5. vector<int> path;
  6. void backtracking(int n, int k, int startIndex) {
  7. if (path.size() == k) {
  8. res.push_back(path);
  9. return ;
  10. }
  11. for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {
  12. path.push_back(i);
  13. backtracking(n, k, i + 1);
  14. path.pop_back();
  15. }
  16. }
  17. public:
  18. vector<vector<int>> combine(int n, int k) {
  19. backtracking(n, k, 1);
  20. return res;
  21. }
  22. };

今日总结:

有新的任务了,往后刷题可真就是海绵里挤水,时间变得更加宝贵==

学到兴致处时常感慨,时间过得太快了,想学的都学不完。

关于回溯:

在二叉树的基础上,理解还行,就是剪枝的条件有一点点没懂,看讲解能明白,自己想不一定写出来

另外在组合问题上,需要注意它不需要考虑元素的顺序,所以代码中startIndex的出现,就是标记N叉树下一层所需要选择的起始位置,每次都在前一层的基础上加1。

标签:int,res,随想录,back,77,算法,vector,path,backtracking
From: https://www.cnblogs.com/ucaszym/p/17099955.html

相关文章