39. Combination Sum 回溯算法简析

标签: leetcode  回溯法  深度优先

LeetCode传送门

    这道题要求给你一组正数 C,然后给你一个目标数 T,让你从那组C中找到加在一起等于 T 的那些组合。

    例如:给你 [2,3,6,7] 和 7,则返回 [[2,2,3],[7] ] 。 

    想解决这个问题前,我们首先引入一个新问题,图(树)的遍历问题。

    

    假如我们想要深度优先遍历这个树,返回[ [2,2,2,2] , [2,2,2,3] , [...] ... ],我们需要从左边一直访问下去,进入第四层,得到[2, 2, 2, 2],然后返回到第三层得到 [2, 2, 2 ],再进入到第四层,得到 [2, 2, 2, 3] ... 得到[ 2, 2, 2, 7 ]之后,第三层的 “2” 及其子树就全部遍历完成,这时候就需要返回到第二层,得到[2,2],进入第三层的 [2, 2, 3] ... 知道全部遍历完成。

    即一个典型的回溯算法,对于回溯算法(探索与回溯法),是一种选优搜索法,又称为试探法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。。

    以深度遍历为例,当访问到第四层时,我们得到了一个正确结果,除了正确结果意外的点,都是“回溯点”。

代码实现:

class Solution(object):
    def SampleHuisu(self, candidates, temp, level, result):
        if level == 4: #正确结果
            result.append(temp[:])
        else:
            for i in candidates:
                if 1: #与之后比较使用
                    temp.append(i)
                    self.SampleHuisu(candidates, temp, level+1, result)
                    temp.pop()

result = []
A = Solution()
A.SampleHuisu([2, 3, 6, 7], [], 0, result)
print(result)

    下面,我们来解决之前的问题,只需要在遍历问题上加一些条件:

    1. 正确结果,应该是遍历得到的节点之和等于 target

    2. 如果遍历得到的节点之和大于 target,则不需要继续向下遍历

    3. 为了保证输出的结果没有重复,我们要求向下遍历时,节点的值必须是非递减的(假设),即不会访问 [2, 2, 3, 2] 或者 [2, 3, 2, ? ] 这样的节点。

    代码如下:

class Solution(object):
    def huisu(self, candidates, temp, target, result):
        sum = 0
        for i in temp:
            sum += i
        if sum >= target:
            if sum == target:
                result.append(temp[:])
        else:
            for i in candidates:
                if temp == [] or i >= temp[-1]:
                    temp.append(i)
                    self.huisu(candidates, temp, target, result)
                    temp.pop()

    def combinationSum(self, candidates, target):
        result = []
        self.huisu(candidates, [], target, result)
        return result

result = []
A = Solution()
result = A.combinationSum([2, 3, 6, 7], 7)
print(result)
    问题解决!
版权声明:本文为weixin_40017590原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_40017590/article/details/79935344

智能推荐

剑指offer 合并两个排序的链表

题目 链接:https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/ 思路 我想的是,与合并两个有序数组一样的思维,新建一个链表,然后判断谁的值大,进而在新的链表上面进行插入。 看书思路 合并链表是一个递归问题:合并一个节点后可以转化为一个子问题。终止条件是其中一个链表为空 代码 链表反转也可以用递归解决...

Java编程思想 第三章:操作符

Java中的操作符和c/c++中的操作符基本一致,因为我之前学习过C语言和C++,所以本章的内容大部分都已熟知,下面只做简单的介绍。 Java操作符及优先级 Java中的操作符包括算术操作符,关系操作符,逻辑操作符,位运算符、自操作运算符、移位运算符、赋值运算符和其他运算符。 算术操作符:包括加减乘除和取余(%),优先级乘除取余高于加减,都是双元运算符,其中加法(+)可以用来连接两个字符串,比如:...

JetBrains 系列开发工具,如何配置 `SCSS` `File Watcher` ,相关输出配置参数详解:webStorm phpStorm IDEA

JetBrains 系列开发工具,如何配置 SCSS File Watcher ,相关输出配置参数详解:webStorm phpStorm IDEA 前言 你目前已经了解了如何使用 SCSS 进行开发,了解了该文章的内容:『 SCSS 日常用法 』 在 JetBrains 系列开发工具中通过 FileWatcher 进行编译的 SCSS 文件都是通过 sass 这个程序进行的。『 如何添加 Fil...

C语言小函数—二进制与十六进制

测试如下 “` int main() { long int num = 15; } “`...

仿微博或微信的文章多图显示(自定义MultiImageView)

按照一般的规矩,先上张图来供大伙看看 如果大致是大伙们需要实现的功能,不烦一观 自定义MultiImageView 工具类 具体使用 app.gradle中添加依赖 implementation 'com.github.bumptech.glide:glide:4.8.0' AndroidManifest.xml中配置联网权限 <uses-permission android:name=&q...

猜你喜欢

经典进程同步和互斥问题

经典进程同步与互斥问题 前言 一、生产者-消费者问题 1.问题描述 2.问题分析 3.代码 二、读者-写者问题 1.问题描述&&分析 2.代码 三、哲学家进餐问题 1.问题描述&&分析 2.代码 四、理发师问题 1.问题描述&&分析 2.代码 前言 在多道程序设计环境中,进程同步是一个非常重要的问题,下面讨论几个经典的进程同步问题。 一、生产者-消费...

java设计模式——ThreadLocal线程单例

1、定义一个ThreadLocal线程单例,代码如下: 2、定义一个多线程类,代码如下: 3、定义一个测试类,代码如下: 4、输出结果,如下图:...

【tensorflow】线性模型实战

线性模型:y = 1.477 * x + 0.089   1. 采样数据 采样噪声eps在均值0,方差0.01的高斯分布中,而后在均匀分布U(0,1)中,区间[-10,10]进行n=100次随机采样:   2. 计算误差 循环计算每个点的预测值与真是值之间差的平方并累加,从而获得训练集上的均芳误差损失值。   3. 计算梯度   4. 梯度更新 对权重w和偏...

常见损失函数和评价指标总结(附公式&代码)

网上看到一篇很实用的帖子关于常见损失函数和评价指标,收藏下来 本文转载于https://zhuanlan.zhihu.com/p/91511706 ------------------------------------------------------------------------------------------------------------------------------...

为什么 4G/5G 的直播延时依然很高

通信技术的发展促进了视频点播和直播业务的兴起,4G 和 5G 网络技术的进步也使得流媒体技术变得越来越重要,但是网络技术并不能解决流媒体直播的高延迟问题。 本文不会介绍网络对直播业务的影响,而是会分析直播中常见的现象 — 主播和观众之间能够感觉到的明显网络延迟。除了业务上要求的延迟直播之外,有哪些因素会导致视频直播的延迟这么高呢? live-streaming  图 1 - ...