开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 算法刷题总结 (二)回溯算法 -> 正文阅读

[数据结构与算法]算法刷题总结 (二)回溯算法

一、理解回溯算法

1.1、回溯的概念

回溯是递归的纵横拓展，主要是递归（纵）+局部暴力枚举（横）。所以可以从递归和暴力两个方面来拆解回溯问题。
在这里插入图片描述
由上图可知，回溯法的所有问题都可以抽象为树形结构，集合的大小构成了树的宽度，递归深度构成了树的深度（N叉树）。因为递归有终止条件，所以树的高度会有限，同时递归的最终结果会呈现在叶子节点上。

1.2、回溯法的效率

从上一节的概念可知，回溯=递归+暴力搜索，所以它并不是一个特别高效的算法，即便再做一些剪枝优化下，依旧改变不了它的整体就是穷举的特性。

但即便这个算法效率不高，它的使用依旧很广泛，因为很多问题除了穷举，实在就是没有别的解决办法了，具体可以看看下一章的例题感受下。

1.3、回溯法问题分类

回溯法主要解决以下五种问题：

问题	描述
组合问题	N个数里面按一定规则找出k个数的集合
切割问题	一个字符串按一定规则有几种切割方式
子集问题	一个N个数的集合里有多少符合条件的子集
排列问题	N个数按一定规则全排列，有几种排列方式
棋盘问题	N皇后，解数独，迷宫等等

1.4、回溯法的做题步骤

回溯法三部曲：

回溯函数的模板，返回值以及参数
这里回溯函数起名为backtracking，回溯算法中函数返回值一般为空。
对于参数的话，很难提前确定下来，一般是先写逻辑，然后需要什么参数，就填什么参数。

def backtracking(参数):

回溯函数终止条件
什么时候达到了终止条件，树中就可以看出，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。

if 终止条件:
	保存结果
	return

回溯搜索的遍历过程

# 横向遍历。一个节点有多少个孩子就执行多少次
for i in [本层集合中的元素（树中及节点孩子的数量就是集合的大小）]:
	处理节点
	# 纵向遍历，自己调用自己实现递归
	backtracking(路径，选择列表)
	回溯，撤销处理结果

总结：

def backtracking(参数):
	if 终止条件:
		存放结果
		return
		
	for i in [本层集合中的元素（树中及节点孩子的数量就是集合的大小）]:
		处理节点
		# 纵向遍历，自己调用自己实现递归
		backtracking(路径，选择列表)
		回溯，撤销处理结果

二、经典问题

2.1、组合问题

2.1.1、77. 组合

力扣题目链接

1.使用函数：
itertools库下的combinations组合函数，与之对应的是permutations排列函数。

from itertools import combinations
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        l = [i+1 for i in range(n)]
        res = combinations(l, k)
        return list(res)

2.回溯法：
从题目可以知道，k=2两层循环解决，k=3三层循环，但是题目的k是变动的，也就是for循环的层数是需要是变动的，那么回溯法就用递归来解决层数嵌套，每递归一次就是一层for循环，一个简单的过程如下：
在这里插入图片描述
n相当于树的宽度，k相当于树深度的

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        # 存放符合条件结果的集合
        result = []
        # 存放符合条件单一结果
        path = []
        # startIndex来记录下一层递归，搜索的起始位置
        def backtracking(n, k, startIndex):
            if len(path)==k:
            	# 这里注意要添加一个path的拷贝，直接append为原址
            	# path最后会被pop，结果为空值
                result.append(path[:])
                return
            for i in range(startIndex, n+1):
                path.append(i)
                backtracking(n, k, i+1)
                path.pop()
        backtracking(n, k, 1)
        return result

加上剪枝操作：
如果for循环选择的起始位置之后的元素个数已经不足我们需要的元素个数了，那么就没有必要搜索了。那么后面这些部分可以剪掉，如下，只用更改循环的终止条件改变范围就行。

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        # 存放符合条件结果的集合
        result = []
        # 存放符合条件单一结果
        path = []
        # startIndex来记录下一层递归，搜索的起始位置
        def backtracking(n, k, startIndex):
            if len(path)==k:
                result.append(path[:])
                return
            # n = 4, k = 2, 当len(path) = 1 时
            # 4 - (2 - 1) +1 = 4，从startindex到4都是可以取的
            endIndex = n - (k-len(path))+1
            for i in range(startIndex, endIndex+1):
                path.append(i)
                backtracking(n, k, i+1)
                path.pop()
        backtracking(n, k, 1)
        return result

2.1.2、216.组合总和III

力扣题目链接

1.使用函数：

from itertools import combinations
class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        res = []
        l = combinations([i+1 for i in range(9)], k)
        for i in list(l):
            if sum(i)==n:
                res.append(i)
        return res

2.回溯搜索：

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        path = []
        res = []
        def backtracking(k, n, startIndex):
            if len(path)==k and sum(path)==n:
                res.append(path[:])
            for i in range(startIndex, 10):
                path.append(i)
                backtracking(k, n, i+1)
                path.pop()
        backtracking(k, n, 1)
        return res

加上两次剪枝：

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        path = []
        res = []
        def backtracking(k, n, startIndex):
            # 剪枝1，大于目标值，再遍历也没意义，直接去掉
            if sum(path)>n:
                return
            if len(path)==k and sum(path)==n:
                res.append(path[:])
                return
            # 剪枝2，需要搭配剪枝1，否则k-len(path)会为负数，循环次数反而会增加
            endIndex = 9 - (k-len(path))+1
            for i in range(startIndex, endIndex+1):
                path.append(i)
                backtracking(k, n, i+1)
                path.pop()
        backtracking(k, n, 1)
        return res

本题与77.组合 加了元素总和的限制，同样的，把问题抽象为树形结构，按照回溯算法的步骤走，最后给出剪枝的优化。

2.1.3、17. 电话号码的字母组合

力扣题目链接

回溯法：

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        d = {'2':'abc', '3':'def', '4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs','8':'tuv','9':'wxyz'}
        # 存储根节点
        path = []
        # 存储最终结果
        res = []

        # 回溯数字
        def backtracking(digits):
            if len(digits)==0:
                # 去除空值，非空则添加字符串
                if path:
                    res.append(''.join(path[:]))
                return
            # 循环取一个数字对应的字母
            for i in d[digits[0]]:
                # 存一个该数字的字母
                path.append(i)
                # 去除第一个数字，后面的数字串
                backtracking(digits[1:])
                path.pop()
        
        backtracking(digits)
        return res

在这里插入图片描述
注意：输入1 * #按键等等异常情况。代码中最好考虑这些异常情况，但题目的测试数据中应该没有异常情况的数据，但是要知道会有这些异常，如果是现场面试中，就一定要考虑到。

2.1.4、39. 组合总和

力扣题目链接

回溯法1：

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        path = []
        res = []

        def backtracking(candidates):
        	# 大于目标值直接返回空
            if sum(path)>=target:
                if sum(path)==target and sorted(path) not in res:
                	# 值存进去之前，提前排序，便于去重
                    res.append(sorted(path[:]))
                return
			# 循环整个列表（注意这里会产生重复结果，只是顺序不同）
            for i in candidates:
                path.append(i)
                backtracking(candidates)
                path.pop()
        
        backtracking(candidates)
        return res

回溯法2：
这里加上循环的起始索引，并引入一个su_m变量去存储每一步的sum。

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        path = []
        res = []

        def backtracking(candidates, su_m, startIndex):
            # 因为循环进行了优化，所以这里判断会简单许多
            if su_m>=target:
                if su_m==target:
                    res.append(path[:])
                return
            # [2,3,5,7], 7
            # 这种循环索引而不是列表值，会优先考虑重复
            # 所以不会出现[2,3,2]和[3,2,2]这种重复的排列
            # 优先[2,2,2,2]得不到target开始pop
            for i in range(startIndex, len(candidates)):
                su_m += candidates[i]
                path.append(candidates[i])
                # 这里起始索引为i，因为可以重复使用
                backtracking(candidates, su_m, i)
                # 回溯要减去值
                su_m -= candidates[i]
                path.pop()
        
        backtracking(candidates, 0, 0)
        return res

回溯1会产生排列,要去重，而回溯2只产生组合。
在这里插入图片描述
剪枝优化：
当判断sum > target后，就没有必要进入下一层递归。

对总集合排序之后，如果下一层的sum（就是本层的 sum + candidates[i]）已经大于target，就可以结束本轮for循环的遍历。
在这里插入图片描述

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        path = []
        res = []

        def backtracking(candidates, su_m, startIndex):
            if su_m==target:
                res.append(path[:])
                return

            for i in range(startIndex, len(candidates)):
                # 排序后，小的值的和都大于target，后续大的无序继续
                # 不排序，结果会出问题
                if su_m + candidates[i]> target:
                    return
                su_m += candidates[i]
                path.append(candidates[i])
                backtracking(candidates, su_m, i)
                su_m -= candidates[i]
                path.pop()
        # 注意要排序
        candidates.sort()
        backtracking(candidates, 0, 0)
        return res

2.1.5、40.组合总和II

力扣题目链接

回溯法1（超时）：
把所有组合求出来，去除重复的。

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        path = []
        res = []
        
        def backtracking(candidates, su_m, startIndex):
            # 这里会有重复的，如[1,1,2,5,6,7,10],8
            # 第一个1与第二个1意义不同，[1,2,5] 和 [1,2,6], [1,7]和[1,7]
            # 但对结果来说相同。
            if su_m == target and path[:] not in res:
                res.append(path[:])
                return 
            for i in range(startIndex, len(candidates)):
                if su_m + candidates[i]>target:
                    return
                su_m += candidates[i]
                path.append(candidates[i])
                backtracking(candidates, su_m, i+1)       
                su_m -= candidates[i]
                path.pop()
        candidates.sort()
        backtracking(candidates, 0, 0)
        return res

这里会有重复的，如[1,1,2,5,6,7,10],8。

第一个1与第二个1意义不同，[1,2,5] 和 [1,2,6], [1,7]和[1,7]，但对结果来说相同。

所以，只需要第一次的1就可以，同一树层，第一次出现的重复元素会遍历到后面的重复元素，记一次就行，树层的其他相同的直接去掉。

回溯法2（使用startIndex去重）：
既然求结果去重会超时，那么就需要在求的过程中提前去重。

这里直接使用startIndex进行判断去重，同一个树层(for循环内)和上一个元素相等则continue跳过。

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        path = []
        res = []
        
        def backtracking(candidates, su_m, startIndex):
            # 这里会有重复的，如[1,1,2,5,6,7,10]
            # 第一个1与第二个1意义不同，但对结果来说相同
            if su_m == target and path[:] not in res:
                res.append(path[:])
                return 
            for i in range(startIndex, len(candidates)):
                if su_m + candidates[i]>target:
                    return
                # 只是用索引来判断重复，
                if i>startIndex and candidates[i] == candidates[i-1]:
                    continue
                su_m += candidates[i]
                path.append(candidates[i])
                backtracking(candidates, su_m, i+1)       
                su_m -= candidates[i]
                path.pop()
        candidates.sort()
        backtracking(candidates, 0, 0)
        return res

回溯法3（新建used数组去重）：
used[i - 1] == true，说明同一树枝candidates[i - 1]使用过，纵向
used[i - 1] == false，说明同一树层candidates[i - 1]使用过，横向

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        path = []
        res = []
        used = [False] * len(candidates)
        
        def backtracking(candidates, su_m, startIndex):
            # 这里会有重复的，如[1,1,2,5,6,7,10]
            # 第一个1与第二个1意义不同，但对结果来说相同
            if su_m == target and path[:] not in res:
                res.append(path[:])
                return 
            for i in range(startIndex, len(candidates)):
                if su_m + candidates[i]>target:
                    return
                # 上个相同节点没使用过，为False，可以判断为同一树层，则跳过
                # 上个相同节点使用过，为True，可以判断为同一树枝，不跳
                if i>0 and candidates[i] == candidates[i-1] and used[i-1]==False:
                    continue
                    
                used[i]=True
                su_m += candidates[i]
                path.append(candidates[i])
                backtracking(candidates, su_m, i+1)    
                # 回溯，为了下一轮for loop   
                used[i]=False
                su_m -= candidates[i]
                path.pop()
        candidates.sort()
        backtracking(candidates, 0, 0)
        return res

在这里插入图片描述

2.2、分割问题

2.2.1、131. 分割回文串

力扣题目链接

回溯法：

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        res = []
        path = []
        # 判断回文的函数
        # 正反序
#        def isPalindrome(s, start, end):
#            if s[start:end+1] == s[start:end+1][::-1]:
#                return True
#            return False
        # 双指针
        def isPalindrome(s, start, end):
            while start<end:
                if s[start] != s[end]:
                    return False
                start+=1
                end-=1
            return True
        def backtracking(s, startIndex):
            if startIndex>= len(s):
                res.append(path[:])
                return
            for i in range(startIndex, len(s)):
                # 判断是否为回文，是再添加到path
                # 不是回文，则切割失败，后续操作跳过
                if isPalindrome(s, startIndex, i):
                    path.append(s[startIndex:i+1])
                else:
                    continue
                backtracking(s, i+1)
                path.pop()
        
        backtracking(s, 0)
        return res

在这里插入图片描述

2.2.2、93.复原IP地址

力扣题目链接

回溯法：
思路同上一题，切割成4份为终止标准，结合startIndex判断是否遍历完整字符串，将合法的结果用’.'拼接即可。

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        res = []
        path = []
        # 判断是否合法
        # 1. 0-255 之间，闭区间
        # 2. 当长度大于1时(或不为0)，首位不能为0
        def isValid(s, start, end):
            if 0<=int(s[start:end+1])<=255 and \
            (s[start:end+1]=='0' or s[start:end+1].lstrip('0')==s[start:end+1]):
                # 首位不能为0，则去除首位的0后还是原来的字符串则首位无0
                return True
            return False

        def backtracking(s, startIndex):
            # 终止条件为截取了4段
            if len(path)==4:
                # 截取4段，并且索引到了尾部，即取了所有字符
                if startIndex == len(s):
                    # 将结果用.拼接起来
                    res.append('.'.join(path[:]))
                return 
            # 遍历字符串
            for i in range(startIndex, len(s)):
                if isValid(s, startIndex, i):
                    path.append(s[startIndex:i+1])
                # 不合法后续操作直接终止
                else:
                    return
                backtracking(s, i+1)
                path.pop()
        
        backtracking(s, 0)
        return res

在这里插入图片描述

2.3、子集问题

2.3.1、78. 子集

力扣题目链接
注：幂集就是集合的所有子集。

回溯法：

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        path = []

        def backtracking(nums, startIndex):
            # 子集就是遍历整个树
            res.append(path[:])
            if startIndex == len(nums):
                return

            for i in range(startIndex, len(nums)):
                path.append(nums[i])
                backtracking(nums, i+1)
                path.pop()
        
        backtracking(nums, 0)
        return res

在这里插入图片描述
从上图可知，求取子集问题，不需要任何剪枝，因为子集就是要遍历整棵树。

2.3.2、90. 子集 II

力扣题目链接
思路同 40. 数组总和 II，即去重，去掉同一树层的重复节点。

回溯法：

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res = []
        path = []

        def backtracking(nums, startIndex):
            res.append(path[:])
            if startIndex == len(nums):
                return
            
            for i in range(startIndex, len(nums)):
                # 同一树层，相似的则先去掉
                if i>startIndex and nums[i]==nums[i-1]:
                    continue
                path.append(nums[i])
                backtracking(nums, i+1)
                path.pop()
        # 需要排序，便于把相似的排到一起
        nums.sort()
        backtracking(nums, 0)
        return res

在这里插入图片描述

2.4、排列问题

排列是有序的，也就是说 [1,2] 和 [2,1] 是两个集合，这和之前分析的子集以及组合所不同的地方。

2.4.1、46.全排列

力扣题目链接

回溯法1，数组截断传递：

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        path = []

        def backtracking(nums):
            # 每次传入的nums是变动的，逐渐变为空，所以不能len(path)==len(nums)
            if not nums:
                res.append(path[:])
                return
            # 从索引0开始，因为每次都要取到所有数
            for i in range(len(nums)):
                path.append(nums[i])
                # 去掉被选中的nums[i]，选取其他段拼在一起
                backtracking(nums[:i]+nums[i+1:])
                path.pop()
        backtracking(nums)
        return res

回溯法2，used数组：

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        path = []
		# 创建一个flag数组，保存结果，是否使用过
        used_list = [False]*len(nums)

        def backtracking(nums, used_list):
            # 每次传入的nums是固定的，则len(path)==len(nums)
            if len(path) == len(nums):
                res.append(path[:])
                return
            for i in range(len(nums)):
                # 已经使用过，则去重
                if used_list[i]==True:
                    continue
                used_list[i] = True
                path.append(nums[i])
                
                backtracking(nums, used_list)

                used_list[i] = False
                path.pop()
        backtracking(nums, used_list)
        return res

回溯法3，去掉used：
最简单的写法，因为无重复元素，所以path可以代替used_list。

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        path = []

        def backtracking(nums):
            # 每次传入的nums是固定的，则len(path)==len(nums)
            if len(path) == len(nums):
                res.append(path[:])
                return
            for i in range(len(nums)):
                # 因为本题为无重复元素，所以path内的元素是唯一的
                if nums[i] in path:
                    continue
                
                path.append(nums[i])
                
                backtracking(nums)

                path.pop()
        backtracking(nums)
        return res

在这里插入图片描述
可以看出元素1在[1,2]中已经使用过了，但是在[2,1]中还要在使用一次1，所以处理排列问题就不用使用startIndex了。

排列问题的不同：

每层都是从0开始搜索而不是startIndex
需要used数组记录path里都放了哪些元素了

2.4.2、47.全排列 II

力扣题目链接

这里去重不是用set，而是used_list和num[i]==num[i-1]判断值是否相等。

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res = []
        path = []
        used_list = [False]*len(nums)
        
        def backtracking(nums, used_list):
            if len(nums) == len(path):
                res.append(path[:])
                return
    
            for i in range(len(nums)):
                # 每次递归，都是所有元素
                # 1.该元素自身被使用过，continue
                if used_list[i] == True:
                    continue
                # 2.该元素同一层有之前有重复，则只算一次，则这一次continue
                # used_list[i-1]==True表示同一层之前使用过
                if (i>0 and nums[i]==nums[i-1]) and used_list[i-1]==True:
                    continue
                used_list[i] = True
                path.append(nums[i])
                backtracking(nums, used_list)
                used_list[i] = False
                path.pop()
        nums.sort()
        backtracking(nums, used_list)
        return res

在这里插入图片描述

2.5、棋盘问题

2.5.1、51. N 皇后

力扣题目链接

回溯法：

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        res = []
        board = [['.']*n for _ in range(n)]

        # 判断是否合法
        def isVaild(board, row, col):
            # 1. 判断同一列是否冲突
            for i in range(row+1):
                if board[i][col] == 'Q':
                    return False
            # 2.判断左上是否冲突
            tmp_row = row
            tmp_col = col
            while 0<=tmp_row<n and 0<=tmp_col<n:
                
                if board[tmp_row][tmp_col]== 'Q':
                    return False
                tmp_row-=1
                tmp_col-=1

            # 3.判断右上是否冲突
            tmp_row = row
            tmp_col = col
            while 0<=tmp_row<n and 0<=tmp_col<n:
                if board[tmp_row][tmp_col]== 'Q':
                    return False
                tmp_row-=1
                tmp_col+=1
            
            return True

        # 每一行进行遍历
        def backtracking(row, board):
            if row == n:
                tmp = []
                for i in board:
                    tmp.append(''.join(i))
                res.append(tmp)
                return
            # 每一行的每一列进行选取
            for col in range(n):
                if not isVaild(board, row, col):
                    continue
                board[row][col] = 'Q'
                # 进入下一行
                backtracking(row+1, board)
                board[row][col] = '.'
                
        
        backtracking(0, board)
        
        return res

在这里插入图片描述
皇后们的约束条件：

不能同行
不能同列
不能同斜线

符合条件则继续下一行，否则同行的下一列。

2.5.2、37. 解数独

力扣题目链接

回溯法：

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        def isVaild(row, col, val, board):
            # 判断同一行是否冲突
            for i in range(9):
                if board[row][i] == str(val):
                    return False
            # 判断同一列是否冲突
            for i in range(9):
                if board[i][col] == str(val):
                    return False
            # 判断同一宫是否冲突
            start_row = (row//3)*3
            start_col = (col//3)*3
            for i in range(start_row, start_row+3):
                for j in range(start_col, start_col+3):
                    if board[i][j] == str(val):
                        return False
            return True


        # 若有解返回True，无解返回False
        def backtracking(board):
            # 遍历整个表，行和列
            for i in range(len(board)):
                for j in range(len(board[0])):
                    # 若空格内已经有数字，则跳过
                    if board[i][j] != '.':
                        continue
                    # 逐渐填入1-10
                    for k in range(1, 10):
                        # 有效则继续递归
                        if isVaild(i, j, k, board):
                            board[i][j] = str(k)
                            if backtracking(board):
                                return True
                            # 回溯
                            board[i][j] = '.'
                    # 若数字1-9都不能成功填入空格，返回False无解
                    return False
            # 有解
            return True
        backtracking(board)

在这里插入图片描述
N皇后问题是因为每一行每一列只放一个皇后，只需要一层for循环遍历一行，递归来来遍历列，然后一行一列确定皇后的唯一位置。

本题就不一样了，本题中棋盘的每一个位置都要放一个数字，并检查数字是否合法，解数独的树形结构要比N皇后更宽更深。

这里需要的是一个二维的递归（也就是两个for循环嵌套着递归）

一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，一行一列确定下来之后，递归遍历这个位置放9个数字的可能性。如果一行一列确定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解。

判断棋盘是否合法有如下三个维度：

同行是否重复
同列是否重复
9宫格里是否重复

2.6、其他问题

2.6.1、491.递增子序列（和子集问题很像）

力扣题目链接

本题求自增子序列，是不能对原数组经行排序的，排完序的数组都是自增子序列了，所以不能使用之前的去重逻辑！

回溯法+集合去重：
#深度遍历中每一层都会有一个全新的usage_list用于记录本层元素是否重复使用

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        res = []
        path = []

        def backtracking(nums, startIndex):
            if len(path)>=2:
                res.append(path[:])
            if startIndex==len(nums):
                return
            # 这里要放在内部，因为每一层子树都要去重
            # 用来记录非重复的元素，用来去重判断
            used_list = set()
            # 单层递归逻辑
            # 深度遍历中每一层都会有一个全新的usage_list用于记录本层元素是否重复使用
            for i in range(startIndex, len(nums)):
                # 这个去重只能判断排序后相邻的数组
                # 所以像[4,7,6,7]在这里不可用
                #if i>startIndex and if nums[i] == nums[i-1]:
                #        continue

                # path非空，且后一个小于前一个，即小于path的最后一个元素 
                # 或者 同一树层后面重复出现，不同于前面的相邻重复出现
                if (path and nums[i]<path[-1]) or nums[i] in used_list:
                    continue
                used_list.add(nums[i])
                path.append(nums[i])
                backtracking(nums, i+1)
                path.pop()
        
        backtracking(nums, 0)
        return res

回溯法+哈希表去重：

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        res = []
        path = []

        def backtracking(nums, startIndex):
            if len(path)>=2:
                res.append(path[:])
            if startIndex==len(nums):
                return
            # 使用哈希表去重，也就是数组或列表
            used_list = [False] * 201  # 使用列表去重，题中取值范围[-100, 100]
            
            for i in range(startIndex, len(nums)):
                if (path and nums[i]<path[-1]) or used_list[nums[i]+100]==True:
                    continue
                # +100，将-100 - 100变为0 - 200
                used_list[nums[i]+100] = True
                path.append(nums[i])
                backtracking(nums, i+1)
                path.pop()
        
        backtracking(nums, 0)
        return res

在这里插入图片描述
在图中可以看出，同一父节点下的同层上使用过的元素就不能在使用了。与前面的同一层相邻重复的不同。

2.6.2、332.重新安排行程

力扣题目链接

回溯法1（普通解法，超时）：

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        res = []
        path = []
        used_list = [False]*len(tickets)

        def backtracking(tickets):
            if len(path) == len(tickets):
                res.append(path[:])
                return
            # 每次遍历整个list，前面的通用解法，但对于这一题，这样会超时
            for i in range(len(tickets)):
                if used_list[i] == True:
                    continue
                if i>0 and tickets[i] == tickets[i-1] and used_list[i-1]==True:
                    continue
                
                if (path and (path[-1][-1]==tickets[i][0])) or (not path and tickets[i][0] == 'JFK'):
                    used_list[i] = True
                    path.append(tickets[i])
                    backtracking(tickets)
                    used_list[i] = False
                    path.pop()

        backtracking(tickets)
        
		# 将结果按字典排序
        final = sorted(res)[0]
        r = []
        # 所有list只取第一个值，加上最后一个list取最后一个值
        for i in range(len(final)):
            r.append(final[i][0])

            if i == len(final)-1:
                r.append(final[i][1])
        return r

回溯法2：
重新设置tickets为一个新的对象进行简化处理，这样就无需遍历整个tickets。

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        res = []
        path = ['JFK']
        # 创建一个空字典，值为空list
        ticket_dict = defaultdict(list)
        for item in tickets:
            ticket_dict[item[0]].append(item[1])
        '''
        tickets_dict里面的内容是这样的
         {'JFK': ['SFO', 'ATL'], 'SFO': ['ATL'], 'ATL': ['JFK', 'SFO']})
        '''
        # 根据字典的key去延伸到value再对应到下一个key......以此类推
        def backtracking(start_point):
            if len(path) == len(tickets)+1:
                return True
            ticket_dict[start_point].sort()
            for _ in ticket_dict[start_point]:
                # 取出一个值，选择一个落地点
                end_point = ticket_dict[start_point].pop(0)
                path.append(end_point)

                # 只要找到一个就可以返回了
                if backtracking(end_point):
                    return True
                path.pop()
                ticket_dict[start_point].append(end_point)

        backtracking('JFK')
        return path

在这里插入图片描述

有无序？

变量	有序(或无序能变成有序)	代表	无序(不能变为有序)	代表
去重状态变量(used)	可以不使用；如果使用，放回溯函数外面，代表树层的整体改变	[ ]列表	必须使用，去重状态存储变量，放回溯函数里面	[ ]哈希，{}集合

排列或组合？

变量	排列	组合	幂集
startIndex	结果为树的最后一层孩子。排列问题[1, 2]和[2, 1]不同	树最后一层的第一个孩子。组合问题[1,2]和[2,1]相同	树的每一个节点，包括中间节点，根节点和最后一层孩子
应用	全排列则无startIndex，回溯的循环一直从0开始，每次回溯遍历整个list，去掉遍历过的；非全排列则同组合一样startIndex累加递进，一般出现较少。	全组合只有一种，所以一般无全组合问题，都是N中取m个值组合，startIndex一般累加递进。	当数组无重复元素，幂集的结果大小为 $2^{数组长度}$