leetcode 回溯算法总结（python）

回溯使用的场景：

回溯法非常适合由多个步骤组成的问题，并且每个步骤都有多个选项，当我们在某一步选择了其中一个选项时，就进入下一步，然后又面临新的选项。我们就这样重复选择着，直至到达最后的状态。

一般画树状图表示

做回溯的题步骤：【树的深度遍历过程】

画图，观察元素是否有重复，如有重复则需要剪枝，思考如何剪枝
回溯三要素：路径、选择列表、结束条件
按照此代码模板，写出代码。

经验：在做选择后还要撤销选择，如果做出的选择写在函数列表里如backtrack(path + [num[i]], num[:i] + num[i+1:])，那么无需撤销操作，如果写在外面如path.append(nums[i])，这样就需要撤销上一步的操作。对于树来说，是一个节点一个节点的处理的，我通常习惯用第一种，将选择后的路径放在函数里。如果选用第二种，那么需要撤销操作

需要认真思考剑指offer面试题中的二叉树路径和和矩阵中的路径

【https://mp.weixin.qq.com/s__biz=MzAxODQxMDM0Mw==&mid=2247484709&idx=1&sn=1c24a5c41a5a255000532e83f38f2ce4&chksm=9bd7fb2daca0723be888b30345e2c5e64649fc31a00b05c27a0843f349e2dd9363338d0dac61&scene=21#wechat_redirect】

算法框架

废话不多说，直接上回溯算法框架。解决一个回溯问题，实际上就是一个决策树的遍历过程。你只需要思考 3 个问题：

1、路径：也就是已经做出的选择。

2、选择列表：也就是你当前可以做的选择。

3、结束条件：也就是到达决策树底层，无法再做选择的条件。

代码方面，回溯算法的框架：

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」，特别简单。

剪枝方法：

全排列里面的剪枝，只需要考虑后面的元素和第一个元素相同的情况，则continue。但是要注意是要保证同层不同和上下层相同（i > start），详见leetcode40.总结
对于全排列题不适合用mark，mark用在矩阵中元素只访问一次的情况下如访问矩阵里的坐标或者字母题。

注意事项

1.如果是选择列表循环内需要判断，用continue（表示这步不行还有机会进行下一步），如果是在选择列表循环外判断则用return中断

2.首先对当前路径进行判断，再进入下一个选择列表中。这样可以保证所有的状态都得到判断。

（剑指offer12，13有感而发）

做题顺序

Leetcode:46，47，39，40，78，90，22

剑指offer：12，13

【leetcode46】全排列

#我一直和组合问题看成是一类问题，动作选择弄成start，但是这题，动作选择根本不适合start，因为它还会选取到start之前的动作，因此，这道题应该把动作改成可选择数字的列表。
#这一题没有重复的情况，不需要剪枝。

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
#如果有[1, 2, 3],第一次选择1，之后选择2，3，那么这种可以用start
#但是对于这道题，第一次选择2，第二次可以选择1，3，这种就没必要用start
        result = []
        size = len(nums)
        if size == 0:#终止条件
            return result
        def backtrack(path, nums):
            '''
            :param path: 列表
            :param nums: 动作选择列表
            结束条件：len(path)==size
            '''
            if len(path) == size:
                result.append(copy.deepcopy(path))
                return 
            for i in range(len(nums)):#一层有多少个可能性就有多少个循环
                #path.append(nums[i])
                backtrack(path + [nums[i]], nums[:i]+nums[i+1:])
                #path.pop()#回溯
        backtrack([], nums)
        return result

【leetcode46】全排列2

#回溯+剪枝法
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        result = []
        size = len(nums)
        if size == 0:
            return result

        nums.sort() #提前排序

        def backtrack(path, nums):
            if len(path) == size:
                result.append(copy.deepcopy(path)) #注意这必须是深复制，防止递归过程中对它影响
                return
            for i in range(len(nums)):#每一层有几种情况循环几次
                if i > 0 and nums[i] == nums[i-1]: #i>0保留第一个，使得重复的数字运行一次【剪枝+边界条件】
                    continue
                #path.append(nums[i])
                backtrack(path + [nums[i]], nums[:i]+nums[i+1:])
                #path.pop()#回溯
        backtrack([], nums)
        return result
#和上一题相比，这题有重复的，因此需要剪枝，并且将序列排序。

【leetcode39】组合

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        size = len(candidates)
        if size == 0:
            return result
        def backtrack(path, start, residue):
            if residue == 0:
                result.append(copy.deepcopy(path))
                return
            if residue < 0:
                return
            for c in range(start, size): #例如一共有[2, 3, 6, 7]第一次选择3，第二次只能从3开始选，就不能倒回去选择2了。
                #residue -= candidates[i] 这样是不对的，不能改变residue的值
                #path.append(candidates[c])
                # print(path)
                backtrack(path + [candidates[c]], c, residue - candidates[c]) ##注意residue-candidate[i]要写在递归函数里面
                #path.pop()
        backtrack([], 0, target)
        return result

【leetcode40】组合2

这道题在第二次做的时候仍然出了问题。问题在于剪枝的条件

if i > start and candidates[i-1] == candidates[i]:
    continue
和中断的条件 if s < 0 or start >= size:

参考这位大佬的，写的非常好https://leetcode-cn.com/problems/combination-sum-ii/solution/xiang-xi-jiang-jie-ru-he-bi-mian-zhong-fu-by-allen/

与上一道题回朔完全相同，差的只是一个如何避免重复的问题

这个避免重复当思想是在是太重要了。

这个方法最重要的作用是，可以让同一层级，不出现相同的元素。但是却允许了不同层级之间的重复

/ \

2 2 这种情况不会发生

/ \

5 5

例2

2 这种情况确是允许的

为何会有这种神奇的效果呢？

首先 cur-1 == cur 是用于判定当前元素是否和之前元素相同的语句。这个语句就能砍掉例1。可是问题来了，如果把所有当前与之前一个元素相同的都砍掉，那么例二的情况也会消失。因为当第二个2出现的时候，他就和前一个2相同了。

那么如何保留例2呢？

那么就用cur > begin 来避免这种情况，你发现例1中的两个2是处在同一个层级上的，

例2的两个2是处在不同层级上的。在一个for循环中，所有被遍历到的数都是属于一个层级的。我们要让一个层级中，必须出现且只出现一个2，那么就放过第一个出现重复的2，但不放过后面出现的2。第一个出现的2的特点就是 cur == begin. 第二个出现的2 特点是cur > begin.

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        size = len(candidates)
        if size == 0:
            return result
        candidates.sort()
        def backtrack(path, start, residue):
            if residue == 0:
                result.append(copy.deepcopy(path))
                return
            if residue < 0 or start >= size:#记得要把所有的中断找全
                return
            for c in range(start, size):
                #如果c必须要先大于start才能保证c-1这个下界。
                if c > start and candidates[c-1] == candidates[c]:#for循环时同一层的，不让同一层的重复，但不同层可以重复。详解见https://leetcode-cn.com/problems/combination-sum-ii/solution/xiang-xi-jiang-jie-ru-he-bi-mian-zhong-fu-by-allen/
                    continue
                #path.append(candidates[c])
                #当有i+1要小心了，start可能会出界，所以加上这个中断条件
                backtrack(path + [candidates[c]], c+1, residue - candidates[c])  
                #path.pop()
        
        backtrack([], 0, target)
        return result

【leetcode78】子集

思路：画出图以后发现，所有的节点都符合要求。因此每一个叶子都加入result

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result = []
        size = len(nums)
        if size == 0:
            return result
        def backtrack(path, start):
            result.append(path)
            if start == size:
                return
            for i in range(start, size):
                backtrack(path+[nums[i]], i+1)
        backtrack([], 0)
        return result

【leetcode90】子集2

又遇到了剪枝的问题。画图发现，1，2，2的时候两个2保留第一个2就行了。

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        result = []
        size = len(nums)
        if size == 0:
            result.append([])
            return 

        nums.sort()

        def backtrack(path, start):
            result.append(path) #每一片叶子都是我要的答案
            if start == size:
                return
            for i in range(start, size):
                if i > start and nums[i-1] == nums[i]: #保证同层不重复，异层可以相同
                    continue
                backtrack(path + [nums[i]], i + 1)
        backtrack([], 0)
        return result

[leetcode79]单词搜索—— [剑指offer]12题

backtrack有返回值的好像就这一道，我觉得还是有难度的哈哈哈哈哈哈。

mark用来标记矩阵元素， 0表示没有访问，1表示访问过了。

思路：

一种是backtrack(i, j, word)对当前i,j进行判断，如果可以往下进行，则下一步，如果不可以，退一步(用mark来表示)
一种是对i,j的下一步cur_i, cur_j进行判断，如果可以往下进行，则下一步，如果不可以，退一步(用mark来表示)

注意：

在backtrack里面，在循环选择列表里只能用continue在循环列表外只能用return。
对于此题来说，找到一个word，摒弃一个，要注意递归的返回值的正确应用。

思路1

class Solution(object):
    def exist(self, board, word):
        row = len(board)
        col = len(board[0])
        if row == 0:
            return False
        mark = [[0 for _ in range(col)] for _ in range(row)]
        def backtrack(i, j, mark, word):
            if len(word) == 0:
                return True
            if not (i >= 0 and j >= 0 and i < row and j < col):
                return False
            if mark[i][j] == 1:
                return False
            if board[i][j] == word[0]:
                mark[i][j] = 1
                #函数有返回值要先赋值。
                fanhuiz = backtrack(i+1, j, mark, word[1:]) or backtrack(i-1, j, mark, word[1:]) or backtrack(i, j-1, mark, word[1:]) or backtrack(i, j+1, mark, word[1:])
                #这个不能直接if not (backtrack(i+1, j, mark, word[1:]) or backtrack(i-1, j, mark, word[1:]) or backtrack(i, j-1, mark, word[1:]) or backtrack(i, j+1, mark, word[1:]))
                if not fanhuiz:
                    mark[i][j] = 0 #回溯，因为这个点没走下去，因此这个点相当于没走
                    return False
                else:
                    return True
            return False
        for i in range(row):
            for j in range(col):
                if backtrack(i, j, mark, word):
                    return True
        return False

思路2：

class Solution(object):
    def exist(self, board, word):
        directs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        row = len(board)
        col = len(board[0])
        if row == 0:
            return False

        def backtrack(i, j, word, mark):
            #中断条件
            if len(word) == 0:
                return True

            for direct in directs: #一层所有的选择（上下左右）
                cur_i = i + direct[0]
                cur_j = j + direct[1]
                
                if cur_i >= 0 and cur_i < row and cur_j >= 0 and cur_j < col and board[cur_i][cur_j] == word[0]:#这句是为了看此时定位的字母是不是word的首字母
                    if mark[cur_i][cur_j] == 1:
                        continue
                    #回溯方法要记住
                    # 将该元素标记为已使用
                    mark[cur_i][cur_j] = 1
                    if backtrack(cur_i, cur_j, word[1:], mark) is True:
                        return True
                    else:
                        mark[cur_i][cur_j] = 0
            return False

        mark = [[0 for _ in range(col)] for _ in range(row)]
        for i in range(row):
            for j in range(col):
                if board[i][j] == word[0]:
                    #回溯方法要记住
                    mark[i][j] = 1
                    if backtrack(i, j, word[1:], mark) == True:#如果一条路走不通就是False
                        return True
                    else:
                        mark[i][j] = 0
        return False

[剑指offer]13题机器人的运动范围

思路1：backtrack无返回值就不用处理了。

class Solution:
    def movingCount(self, threshold, rows, cols):
        self.count = 0
        if rows == 0:
            return self.count
        mark = [[0 for _ in range(cols)] for _ in range(rows)]

        def backtrack(i, j, k):
            if i < 0 or i >= rows or j < 0 or j >= cols:
                return
            if mark[i][j] == 1:
                return
            tmpi = list(map(int, list(str(i))))
            tmpj = list(map(int, list(str(j))))
            if sum(tmpi) + sum(tmpj) > k:
                return
            mark[i][j] = 1
            self.count += 1
            backtrack(i-1, j, k)
            backtrack(i+1, j, k)
            backtrack(i, j-1, k)
            backtrack(i, j+1, k)

        backtrack(0, 0, threshold)
        return self.count

思路2 ：

一定要注意对于初始ij的处理。

class Solution:
    def movingCount(self, threshold, rows, cols):
        directs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        self.count = 0
        if rows == 0:
            return self.count
        mark = [[0 for _ in range(cols)] for _ in range(rows)]
        mark[0][0] = 1
        def backtrack(i, j, k):
            for direct in directs:
                cur_i = i + direct[0]
                cur_j = j + direct[1]
                if not (cur_i >= 0 and cur_i < rows and cur_j >= 0 and cur_j < cols):
                    continue
                i_list = list(map(int, list(str(cur_i))))
                j_list = list(map(int, list(str(cur_j))))
                if sum(i_list) + sum(j_list) > k:
                    continue
                if mark[cur_i][cur_j] == 1:
                    continue
                self.count += 1
                mark[cur_i][cur_j] = 1
                backtrack(cur_i, cur_j, k)
        if threshold > 0:
            self.count = 1
        backtrack(0, 0, threshold)
        return self.count

总结：还有一些小细节，记录一下遇到的坑。1、count= 0必须写成self.count=0，而矩阵list不用。2、如果有bactrack有返回值，在递归判断时应用3、map的对象必须是正整数，不能是负数，因此要先判断i，j是否出界再进得到i_list, j_list。

[leetcode22] 括号的生成

思路：画图，想清楚路径和中断条件。

class Solution:
    def generateParenthesis(self, n: int):
        result = []
        if n == 0:
            return result
        def helper(left, right, path):
            if right > left:
                return
            if left == n and right == n:
                result.append(path[:])
                return
            if left < n:
                helper(left+1, right, path+'(')
            if right < n:
                helper(left, right+1, path+')')
        helper(0, 0, '')
        return result

leetcode 回溯算法总结（python）

回溯使用的场景：

做回溯的题步骤：【树的深度遍历过程】

算法框架

剪枝方法：

注意事项

做题顺序

这道题在第二次做的时候仍然出了问题。问题在于剪枝的条件

继续阅读

YAML简介和PyYAML安全操作YAML支持的类型YAML的优点：yaml的基本语法python操作

Small tricks

libsvm for python 安装

学习软件测试基础测试第七天

Zeppelin 配置访问 REST APIApache Zeppelin Configuration REST API

【Torch】最简洁logging使用指南

笔试面试题目：滑动窗口(二)

27. Remove Element(列表)题目代码

Cloud Studio初体验

使用 ctypes 进行 Python 和 C 的混合编程

【python】【数据处理】画多维数据分布图

LeetCode OJ Binary Tree Right Side View

leetcode809

【python】netconf协议对接管理设备

「Python 网络自动化」NETCONF —— Python 使用 NETCONF 管理配置 H3C 网络设备

在python中创建excel并写入