部分回溯法题解

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

部分回溯法题解,算法题,深度优先,算法,python,pycharm,leetcode


一、22. 括号生成


数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。

示例 1:
输入:n = 3
输出:[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]

示例 2:
输入:n = 1
输出:[“()”]

如果是左括号直接添加
如果是右括号不能超过已经添加的左括号个数
所以:左括号的长度要比右括号的长度大,才可以
思路:采用深度优先加回溯

class S22:
    def generate(self, n):
        res = []

        # 代表左右两边的括号剩余个数,一开始都有n个
        def dfs(left, right, path):  # path:生产括号的路径
            if left == 0 and r == 0:
                res.append(path)
                return
            # 特殊情况:如果用到的右括号已经超过用到的左括号了
            if right < left:
                return
            if left > 0:
                dfs(left - 1, right, path + "(")
            if right > 0:
                dfs(left, right - 1, path + ")")

        dfs(n, n, "")
        return res

二、39. 组合总和

中等
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。
对于给定的输入,保证和为 target 的不同组合数少于 150 个。

示例 1:
输入:candidates = [2,3,6,7], target = 7
输出:[[2,2,3],[7]]
解释:
2 和 3 可以形成一组候选,2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选, 7 = 7 。
仅有这两种组合。

示例 2:
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3:
输入: candidates = [2], target = 1
输出: []

思路:使用回溯法

class Solution39:
    def combination(self, canditates, target):
        if not canditates:
            return []

        # 找到的1个结果存放在path,总的结果存放到res中
        def dfs(res, path, target, index):
            if target == 0:
                res.append(path[:])

            for i in range(index, len(canditates)):
                if target >= canditates[i]:
                    # 如果目标值大于当前值,加入到path中
                    path.append(canditates[i])
                    dfs(res, path, target - canditates[i], i)  # 为什么是i,不是i+1:原因是数组中的元素可以重复取
                    # 重写设置现场
                    path.pop()

        res = []
        dfs(res, [], target, 0)
        return res

部分回溯法题解,算法题,深度优先,算法,python,pycharm,leetcode文章来源地址https://www.toymoban.com/news/detail-828926.html

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

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

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

相关文章

  • 【力扣 51】N 皇后(回溯+剪枝+深度优先搜索)

    按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。 给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。 每一种解法包含一个不同的 n 皇后

    2024年02月22日
    浏览(39)
  • Leetcode题解-算法-动态规划(python版)

    1.1 爬楼梯 70. 爬楼梯(Easy) 走n阶楼梯的方法有两种,1、先走 1 级台阶,再走 n-1 级台阶;2、先走 2 级台阶,再走 n-2 级台阶 f(n) = f(n-1) + f(n-2) 1.2 强盗抢劫 198. 打家劫舍(Medium) 每个房间财产为 nums[0]……nums[n-1]。 假设 0 至 x 间房获得的最大财产为 f(x)。 f(x) = max(f(x-1),f(x-2)+nums[

    2024年02月03日
    浏览(51)
  • 回溯算法之广度优先遍历

    目录 迷宫问题 N叉树的层序遍历  腐烂的橘子 单词接龙  最小基因变化  打开转盘锁 假设有一个迷宫,里面有障碍物,迷宫用二维矩阵表示,标记为0的地方表示可以通过,标记为1的地方表示障碍物,不能通过。现在给一个迷宫出口,让你判断是否可以从入口进来之后,走出

    2024年02月08日
    浏览(26)
  • Python 算法基础篇:深度优先搜索( DFS )和广度优先搜索( BFS )

    深度优先搜索( DFS )和广度优先搜索( BFS )是两种常用的图遍历算法,用于在图中搜索目标节点或遍历图的所有节点。本篇博客将介绍 DFS 和 BFS 算法的基本概念,并通过实例代码演示它们的应用。 😃😄 ❤️ ❤️ ❤️ 深度优先搜索( DFS )是一种用于遍历或搜索图或树

    2024年02月07日
    浏览(67)
  • python算法与数据结构(搜索算法和拓扑排序算法)---深度优先搜索

    了解树/图的 深度遍历,宽度遍历 基本原理; 会使用python语言编写 深度遍历,广度遍历 代码; 掌握 拓扑排序算法 搜索引擎 提到搜索两个子,大家都应该会想到搜索引擎,搜索引擎的基本工作步骤; 网页爬取 — 数据预处理 — 排序 — 查询 第一步,网页爬取,非常重要,

    2024年01月20日
    浏览(51)
  • Python 图算法,图最短路径,图广度优先搜索,图深度优先搜索,图排序

    一、图数据库相关算法 图数据库是一种专门用来存储和处理图数据的数据库系统。它使用图结构来表示数据之间的关联关系,以及节点和边之间的属性信息。以下是一些常用的图数据库算法: 1. 最短路径算法:最短路径算法用于计算图中两个节点之间的最短路径,例如Dijk

    2024年02月15日
    浏览(36)
  • Python算法:深度优先搜索—DFS(模板及其样例)

    • 沿着一条路径一直搜索下去,在无法搜索时,回退到刚刚访问过的节点。 • 并且每个节点只能访问一次。 • 本质上是持续搜索,遍历了所有可能的情况,必然能得到解。 • 流程是一个树的形式,每次一条路走到黑。 • 目的主要是达到被搜索结构的叶结点直到最后一层

    2024年03月24日
    浏览(50)
  • 【Python搜索算法】深度优先搜索(DFS)算法原理详解与应用,示例+代码

    目录 1 基本原理 2 DFS算法流程 3 时间复杂度 4 空间复杂度 5 DFS算法应用案例: 5.1 解决路径查找问题  5.2 解决图的连通性问题 5.3  拓扑排序 5.4  在树结构中进行深度遍历 深度优先搜索(DFS)是一种重要的图遍历算法,用于探索图中的节点和边。 DFS 是一种递归或栈(堆栈)

    2024年02月06日
    浏览(62)
  • 算法第六期——DFS初入门(深度优先搜索)(Python)

    目录   一、蛮力的技术:搜索 1.1、【暴力法】 1.2、蛮力的基本方法——扫描 二、搜索的基本方法 2.1、BFS:一群老鼠走迷宫 2.2、DFS:一只老鼠走迷宫  2.3、BFS和DFS的异同  三、DFS详解 3.1、DFS访问示例 3.2、 DFS基础: 递归和记忆化搜索 3.2.1 递归——斐波那契数列 3.2.2改进递归

    2024年04月13日
    浏览(52)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包