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

智能推荐

双路快速排序法

快速排序法的优化——双路快速排序 上一节我们自己动手写的一个快速排序的算法,在随机数测试中表现得非常好,然而,我们在用高度有序的数组进行测试的时候,发现快速排序的效率变得异常的低下,比归并排序的效率低得多了,近似退回了O(n^2)的复杂度,这是为什么呢?首先让我们来分析一下归并排序的算法思想,归并排序之所以能够达到O(logn)的复杂度,多亏了递归,递归使得把数组不断的二分...

android问题记录

Error: Cannot fit requested classes in a single dex file (# methods: 80441 > 65536) 解决办法: gradle文件的defaultConfig默认配置里面增加...

ROS机器人Diego 1# 利用人工智能 风格迁移技术拍摄不同画风的视频

风格迁移,就是将一种图片的风格迁移到其他图片上,改变其他图片的风格,很好玩的一个人工自能模型,github上已经有很多实现的方法,本文参考https://github.com/hzy46/fast-neural-style-tensorflow 的算法,利用Diego1#的平台实现实时视频的风格转换,先上两张图看效果: 是不是很酷呢,其实实现方法和上篇博文中的原理是一样的,只是把人工智能的算法包装...

猜你喜欢

数据分析学习总结笔记17:文本分析入门案例实战

文章目录 1 数据准备 2 分词 3 统计词频 4 词云 5 提取特征 6 用sklearn进行训练 1 数据准备 数据样例如下, 数据总量为7.7万+: 本节通过一个实战的例子来展示文本分析的最简单流程。首先设定因变量为原始数据中的"评分"。自变量是"评价内容",这里根据评价内容提取TF-IDF特征。之后,通过评价内容的特征建模预测下整体评分。 以上只是最...

LeetCode 150. 逆波兰表达式求值

题目描述 根据逆波兰表示法,求表达式的值。 有效的运算符包括 +, -, *, / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。 整数除法只保留整数部分。 给定逆波兰表达式总是有效的。 换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。 示例 1: 输入:[“2”, “1”, “+”, “3&r...

并查集原理及应用

并查集 树形的数据结构,每个集合有其代表节点,代表节点相同的元素属于同一集合。 find:通过查找节点的代表节点,判断节点所属集合。 union:合并两集合,小集合合并到大集合,使用大集合的代表节点。 在find的递归过程中,让路过节点的父节点直接赋值为代表节点,节省下次查找时间,如图所示。 计算岛的个数 遍历二维数组,遇到1时就将所相连的1都改为2,看看遇到多少次1,就是岛的数量。改数时使用回溯...

linux nutch1.0安装配置

1,下载nutch1.0 下载地址:http://archive.apache.org/dist/nutch/,下载这个文件nutch-1.0.tar.gz   2,上传到服务器 上传位置:/home/www/,解压nutch-1.0.tar.gz #tar -xvf nutch-1.0.tar.gz 重命名 #mv nutch-1.0 nutch   3,修改配置文...

如何搭建自己的博客?附加美化

如何搭建自己的blog?附加美化 前言: 之前在腾讯云以学生优惠租了一年的服务器,还买了一年的域名,忽然觉得不能闲置着域名,所以搭建了个博客,过程也遇到了很多的问题,望在此阐述,予以他人帮助,祝好~ 准备工作:使用Xshell连接上Linux服务器,我的是centos系统,方便进行操作。使用Xftp连接上Linux服务器,方便传输文件。 安装apache服务器:yum install httpd ...