day24 | 回溯算法基础、77. 组合

这篇具有很好参考价值的文章主要介绍了day24 | 回溯算法基础、77. 组合。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录:

解题及思路学习

回溯法理论基础

https://programmercarl.com/回溯算法理论基础.html#题目分类大纲如下

回溯法,一般可以解决如下几种问题:

  • 组合问题:N个数里面按一定规则找出k个数的集合
  • 切割问题:一个字符串按一定规则有几种切割方式
  • 子集问题:一个N个数的集合里有多少符合条件的子集
  • 排列问题:N个数按一定规则全排列,有几种排列方式
  • 棋盘问题:N皇后,解数独等等

**如何理解回溯法:回溯法解决的问题都可以抽象为树形结构。**因为回溯法解决的都是在集合中递归查找子集,集合的大小就构成了树的宽度,递归的深度,都构成的树的深度。递归就要有终止条件,所以必然是一棵高度有限的树(N叉树)。

• 回溯函数模板返回值以及参数:

回溯算法中函数返回值一般为void。函数起名字为backtracking。因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来,所以一般是先写逻辑,然后需要什么参数,就填什么参数。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-76frxxXt-1687574695227)(https://s3-us-west-2.amazonaws.com/secure.notion-static.com/0f08124e-6e33-4b67-8c24-b332b08bd643/Untitled.png)]

从图中看出for循环可以理解是横向遍历,backtracking(递归)就是纵向遍历,这样就把这棵树全遍历完了,一般来说,搜索叶子节点就是找的其中一个结果了。

模板框架:

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
        处理节点;
        backtracking(路径,选择列表); // 递归
        回溯,撤销处理结果
    }
}

77. 组合

给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1:

输入:n = 4, k = 2
输出:
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],]

思考:可以用vector来存储最终的结果。终止条件是当vector的size等于k的时候,就返回。

随想录:

把组合问题抽象为如下树形结构:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CofHOfiE-1687574695232)(https://s3-us-west-2.amazonaws.com/secure.notion-static.com/97cec914-ead1-4ccb-b1f2-ef7c6d6a5987/Untitled.png)]

一开始的集合是1,2,3,4。从左往右取,取过的数,不再重复取。

每次从集合中选取元素,可选择的范围随着选择的进行而收缩,调整可选择的范围

图中可以发现n相当于树的宽度,k相当于树的深度

图中每次搜索到了叶子节点,我们就找到了一个结果

相当于只需要把达到叶子节点的结果收集起来,就可以求得 n个数中k个数的组合集合。

代码:

class Solution {
private:
    vector<vector<int>> result; // 存放符合条件结果的集合
    vector<int> 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:
    vector<vector<int>> combine(int n, int k) {
        result.clear(); // 可以不写
        path.clear();   // 可以不写
        backtracking(n, k, 1);
        return result;
    }
};
  • 时间复杂度: O(n * 2^n)
  • 空间复杂度: O(n)

剪枝优化

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-F1KFKR7h-1687574695233)(https://s3-us-west-2.amazonaws.com/secure.notion-static.com/d53151cf-d1d3-4e19-b1cd-3f8d5da43b49/Untitled.png)]

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

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

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

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

  1. 已经选择的元素个数:path.size();
  2. 还需要的元素个数为: k - path.size();
  3. 在集合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]。

优化后整体代码如下:

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(int n, int k, int startIndex) {
        if (path.size() == k) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) { // 优化的地方
            path.push_back(i); // 处理节点
            backtracking(n, k, i + 1);
            path.pop_back(); // 回溯,撤销处理的节点
        }
    }
public:

    vector<vector<int>> combine(int n, int k) {
        backtracking(n, k, 1);
        return result;
    }
};

这个剪枝优化操作在我看来更像是删掉了构不成条件的循环部分。比如要找的k长度为3,n的长度为4。那么startindex最大也就是2。因为从2之后,比如3开始,后面的数据长度都是小于等于3的,所以直接剪掉这部分。

知识点记录

知识点

1、回溯算法 的基本框架:

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
        处理节点;
        backtracking(路径,选择列表); // 递归
        回溯,撤销处理结果
    }
}

2、剪枝操作原理

个人反思

回溯算法的关键部分是pop()操作文章来源地址https://www.toymoban.com/news/detail-502761.html

到了这里,关于day24 | 回溯算法基础、77. 组合的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 力扣日记1.21-【回溯算法篇】77. 组合

    日期:2023.1.21 参考:代码随想录、力扣 终于结束二叉树了!听说回溯篇也是个大头,不知道这一篇得持续多久了…… 题目描述 难度:中等 给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。 示例 1: 输入:n = 4, k = 2 输出:

    2024年01月22日
    浏览(65)
  • 【力扣】77. 组合 <回溯、回溯剪枝>

    给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按任何顺序返回答案。 示例 1: 输入:n = 4, k = 2 输出: 示例 2: 输入:n = 1, k = 1 输出: 提示: 1 = n = 20 1 = k = n 暴力思考:k 等于多少就是多少层循环。 回溯 回溯法解决的问题都可以抽象为树形结构

    2024年02月12日
    浏览(43)
  • 【数据结构】回溯算法公式化解题 leetcode经典题目带刷:全排列、组合、子集

    一、什么是回溯算法 回溯算法(Backtracking Algorithm)是一种解决 组合问题 、 排列问题 、 选择问题 等一类问题的常用算法。它通过尝试所有可能的选择来找到问题的解,当发现当前选择不符合要求时,就回溯到之前的状态,然后尝试其他的选择。 1、基本思想: 从问题的起

    2024年02月11日
    浏览(45)
  • 77. 组合(回溯)

    和上一道回溯的题思路大致相同: 从前往后依次遍历,之后拼接的数字为当前数字 cur 的之后的数字,直到 list 的长度等于 k ,将 list 加入到 ans 当中。 特别注意: if 和 else 的区分,否则 if 要及时 return 回溯的时候新的 cur 值应该是 i+1 而不是 cur+1 ans.add(new ArrayList(list)); 在

    2024年02月02日
    浏览(46)
  • LeetCode:77. 组合——回溯法,是暴力法?

    🍎道阻且长,行则将至。🍓 🌻算法,不如说它是一种思考方式🍀 算法专栏: 👉🏻123 题目描述 :给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。 来源:力扣(LeetCode) 难度: 中等 提示: 1 = n = 20 1 = k = n 示例 1: 输入:

    2023年04月18日
    浏览(33)
  • DAY25:回溯算法组合题216、17

    经过了昨天组合的题目的学习,这道题比较简单,套用之前的模板就可以 基本思路 终止条件,遇到向量的个数一样,并且sum等于n的时候终止。 输入变量,n,k,还有起始的idx和基于当前元素之和的sum 逻辑就是,按照循环递归下去,注意要对sum值进行回溯。 时间复杂度O(n *

    2024年01月20日
    浏览(37)
  • 代码随想录day24 开启回溯算法

    感觉回溯算法其实和递归很像,也是用递归的做法,也有三部曲,但又不太一样的地方是递归中类似二叉树,只有纵向遍历(一层层往下遍历,没有横向遍历),而回溯算法中多的for循环就是横向遍历,说实话这一点我没有理解的太深,只是知道它类似于两个for循环中的第一

    2024年01月16日
    浏览(53)
  • 【Leetcode60天带刷】day27回溯算法——39. 组合总和,40.组合总和II,131.分割回文串

    ​ 39. 组合总和 给你一个  无重复元素  的整数数组  candidates  和一个目标整数  target  ,找出  candidates  中可以使数字和为目标数  target  的 所有   不同组合  ,并以列表形式返回。你可以按  任意顺序  返回这些组合。 candidates  中的  同一个  数字可以  无限制重复

    2024年02月11日
    浏览(46)
  • Day 25 | 回溯 216.组合总和III 、17.电话号码的字母组合

    题目 文章讲解 视频讲解 思路: 以回溯函数做对称,上面做了什么操作,下面也是 题目 文章讲解 视频讲解 思路:思路上和组合很像,不同的是对字符串进行操作 还得再想想

    2024年01月21日
    浏览(44)
  • 每日OJ题_DFS回溯剪枝⑨_力扣39. 组合总和(两种思路)

    目录 力扣39. 组合总和 解析代码1 解析代码2 39. 组合总和 LCR 081. 组合总和 难度 中等 给你一个  无重复元素  的整数数组  candidates  和一个目标整数  target  ,找出  candidates  中可以使数字和为目标数  target  的 所有   不同组合  ,并以列表形式返回。你可以按  任意顺序

    2024年04月28日
    浏览(32)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包