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

发布时间:2023年12月17日

结束了二叉树的篇章,我们进入到回溯啦!

学习资料:代码随想录 (programmercarl.com)

理论基础

回溯算法又称回溯搜算算法,是一种搜索方法。

作为递归的“副产品”,只要右递归的地方就会有对应的回溯的过程。

回溯算法为纯暴力搜索,不高效,却对解决某些问题很重要。

可以解决的问题:

理解回溯

将回溯法抽象为树形结构,回溯的问题集中在递归查找子集,集合的大小构成了树的宽度,递归的深度构成了树的深度。

回溯算法的Python模板框架如下:

def backtracking(参数):
    if(终止条件):
        存放结果;
        return
for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) :
    处理节点
    backtracking(路径,选择列表)
    回溯,撤销处理结果

题目

77. 组合

题目链接:77. 组合 - 力扣(LeetCode)

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

思路

直接的想法是用for循环,k为几,就嵌套几个for循环,若k很大,这一做法就变得非常繁琐复杂,所以想到用回溯法。?

上面说到要把回溯抽象成属性结构,集合的大小,n为树的宽度,而递归深度为k,是树的深度。

以n为4,k为2为例,树形结构为:

递归就是把暴力枚举法【自动化】了。我们先把数组中前k个元素纳入麾下(由不断在递归中调用递归实现,每次递归添加一个数),然后保持前k-1个数不变,把最后一个替换成新的数(当下最后一层递归因为长度等于k结束后,把最后一个元素弹出)。每次调用递归都要进行一个for循环,调用到结果集的长度为k时为止,所以就相当于进行了k此循环,只是由于递归回溯的操作,代码很简洁。

代码实现

class Solution(object):
    def backtracking(self, n, k, startindex, path, result):
        if len(path) == k:
            result.append(path[:])
            return
        for i in range(startindex, n+1):
            path.append(i)
            self.backtracking(n, k, i+1, path, result)
            path.pop()

    def combine(self, n, k):
        result = []  # 存放结果集
        self.backtracking(n, k, 1, [], result)
        return result

优化版

每次循环没必要从startindex一直遍历到数组最后的元素n。比如k=3, n=5,那么第一层到第三个数就可停止遍历,因为3之后开始最多只有两个数(4,5),小于k。遇到这类代码问题,我总是头大,纠结于区间、加1减1的问题,试着画图解释:

假设要找的个数为3,已经有了1个(即len(path)?= 1),还需取2个(即k-len(path) = 2),那么最后一个能取的数字由黑色的框表示,因为从它到数组最后正好空出了2个,在它前面有n-(k-len(path))个,所以它代表的数是n-(k-len(path))+1(注意不要和数组的序号搞混,我们找的数是从1开始的),又因为Python的for循环是左闭右开的,为了能取到黑框,需再加1,因此代码为:

for i in range(startindex, n-(k-len(path)+2):

完整代码为:?

class Solution(object):
    def backtracking(self, n, k, startindex, path, result):
        if len(path) == k:
            result.append(path[:])
            return
        for i in range(startindex, n-(k-len(path))+2):
            path.append(i)
            self.backtracking(n, k, i+1, path, result)
            path.pop()
            

    def combine(self, n, k):
        result = []  # 存放结果集
        self.backtracking(n, k, 1, [], result)
        return result
        

文章来源:https://blog.csdn.net/Huiwen18/article/details/134973568
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。