image-20240305152953604

回溯算法

回溯算法是一种搜索的方法，在二叉树总结当中，经常使用到递归去解决相关的问题，在二叉树的所有路径问题中，我们就使用到了回溯算法来找到所有的路径。

回溯算法本质就是去穷举，性能并不是那么高效。一般为了提高效率，往往回溯算法会跟剪枝操作相结合。

回溯算法通常可以用来解决一些问题，这也是为什么会有回溯算法的原因

  • 组合问题
    • N个数里面按照一定规则找出k个数的集合。组合不强调元素的顺序
  • 切割问题
    • 一个字符串按一定规则有几种切割方式
      • 分割回文串
      • 复原IP地址
  • 子集问题
    • 一个N个数的集合里有多少符合条件的子集
  • 排列问题
    • N个数按照一定规则全排列，有几种排列方式。排列强调元素的顺序
  • 棋盘问题
    • N皇后、解数独问题

理解回溯

回溯法解决的问题都可以抽象为树形结构，回溯算法解决问题都是在集合中递归查找子集，集合的大小构成了树的宽度，递归的深度构成了树的深度。

递归必须要有终止条件，所以一定是一个高度有限的N叉树。

回溯模板

递归三部曲：

  • 返回值及参数
    • void backtracking(参数)
  • 回溯函数的终止条件
  • 回溯搜索的遍历过程
    • 回溯算法理论基础
1
2
3
4
5
6
7
8
9
10
11
12
void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

练习题

77、组合

image-20231122103657483

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def backtracking(n,k,startindex,path):
            if len(path)==k:
                # 这里需要注意，因为列表在Python中是可变数据类型，后面的修改会导致path变为[]
                res.append(path[:])
                return 
            # 这里的startindex代表的是在单层递归中需要遍历的次数 从startindex一直到n寻找符合条件的数
            for i in range(startindex, n+1):
                path.append(i)
                backtracking(n,k,i+1,path)
                a = path.pop()
        
        res = []
        backtracking(n,k,1,[])
        return res

image-20231122104026446

回溯+剪枝

使用剪枝的原理就在于如果剩余的元素个数已经小于k-len(path)的时候，我们就不再往下继续了。

  1. 已经选择过的元素个数：len(path)
  2. 还需要选择的个数：k-len(path)
  3. 在集合中更需要从最多要从下标为n-(k-len(path))+1开始遍历，在python中因为range循环的时候是左闭右开，所以还需要+1

77.组合4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def backtracking(n,k,startindex,path):
            if len(path)==k:
                # print(path)
                # 这里需要注意，因为列表在Python中是可变数据类型，后面的修改会导致path变为[]
                res.append(path[:])
                return 
           	
            for i in range(startindex, n-(k-len(path))+1+1):
                path.append(i)
                backtracking(n,k,i+1,path)
                # 回溯 退出上一个元素
                path.pop()
        
        res = []
        backtracking(n,k,1,[])
        return res

image-20231125142534496

2024更新代码：【传递的参数不要过多，题目已经给出的参数就不需要再进行传递了】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []

        def backtracking(startIndex, path):
            if len(path) == k:
                res.append(path[:])
                return
            for i in range(startIndex, n - (k - len(path)) + 1 + 1):
                path.append(i)
                backtracking(i + 1, path)
                path.pop()

        backtracking(1, [])
        return res

image-20240313130428518

216、组合总数III

image-20231122174951944

利用回溯代码模板。其中需要注意的是，如果path列表的和已经超过n，那么可以直接进行剪枝，除此之外，如果剩余的数字长度小于k-len(path)的话，就可以不用继续循环了，这一点也方便我们进行剪枝。

递归的三要素

  • 返回值和参数
1
2
def backtracking(n,k,startindex,path):
    pass
  • 递归终止条件
1
2
3
4
5
if sum(path)>n:
    return 
if len(path)==k and sum(path)==n:
    res.append(path[:])
    return
  • 递归体部分
1
2
3
4
for i in range(startindex,9 - (k - len(path)) + 1 + 1):
    path.append(i)
    backtracking(n,k,i+1,path)
    path.pop()

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        def backtracking(n,k,startindex,path):
            # 剪枝
            if sum(path)>n:
                return 
            if len(path)==k and sum(path)==n:
                res.append(path[:])
                return
            for i in range(startindex,9 - (k - len(path))+1+1):
                path.append(i)
                backtracking(n,k,i+1,path)
                path.pop()
        
        res = []
        backtracking(n,k,1,[])
        return res

17、电话号码的字母组合

image-20231122151406020

image-20231122151443212

思路

本题类似于组合问题，需要根据输入的数字对其能够涵盖的字母进行组合，需要解决下面几个问题：

  • 数字和字母如何进行映射
    • 采用一个列表，位置0和位置1的地方空出来，从2开始对应号码上的字母，用字符串表示
  • 两个字母两个for循环，三个字母三个for循环，多个字母多个for循环
  • 输入异常字母如何进行处理？
    • 对于空的digits需要返回一个空列表

递归三要素

  • 递归的参数

参数是digits和index，其中digits是题目给出的字符串，如“23”，而index是记录当前已经遍历到第几个数字了。【实际可以不用digits】

  • 递归结束的条件

如果index的长度和digits长度一样的话，直接return

1
2
3
if index==len(digits):
    res.append(path) # 这里的path被定义为字符串 而字符串在python中是不可变数据类型，因此可以直接用
    return
  • 递归体部分

需要注意的是，回溯的时候对于字符串要想去掉最后一个字符的方法是直接s=s[:-1]。

1
2
3
4
5
6
7
8
# 获取字符串中的数字
mynum = int(digits[index])
# 获取电话号码对应的字符组合
char = myhash[mynum]
for i in range(len(char)):
    path+=char[i]
    backtracking(digits, index+1, path)
    path = path[:-1] # 刨去字符串的最后一个字符

本题是不需要startindex的，因为遍历的不是同一个集合，而是不同的集合。在回溯问题中，如果是遍历同一个集合就需要传递一个参数startindex，用来表示的当前遍历到集合中的第几位。

本题通过index来判断目前遍历到第几个数字，并且index是通过充当函数的参数来实现的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        myhash = ["","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"]
        res = []
        s = ""
        def backtracking(digits, index):
            nonlocal s
            if index==len(digits):
                res.append(s)
                return 
            # digit表示digits中的数字
            digit = int(digits[index])
            # letters表示digit所代表的数字对应的字母有哪些
            letters = myhash[digit]
            # for循环遍历这些字母 
            for i in range(len(letters)):
                s+=letters[i]
                # 进行回溯
                backtracking(digits,index+1)
                s = s[:-1]
        if len(digits)==0:
            return res
        backtracking(digits,0)
        return res

本题有一个需要特殊处理的地方，如果digits为空字符串的话，直接返回空列表，不需要在进行递归回溯了。

image-20231122151431566

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if len(digits)==0:
            return []
        numList = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
        res = []
        s = ""
        def backtracking(index):
            nonlocal s
            if len(digits) == len(s):
                res.append(s)
                return
            digit = int(digits[index])
            chars = numList[digit]
            for i in range(len(chars)):
                s+=chars[i]
                backtracking(index+1)
                s = s[:-1]
        backtracking(0)
        return res

39、组合总数

image-20231122222712060

image-20231122222723187

本题中说了candidates中的同一个数字可以无限制重复被选取，所以我们在进行递归的时候，传递的startindex就是i。

这里需要注意的是：每次需要传入startIndex的原因是可以避免选取之前已经取过的数字

39.组合总和

本题中需要注意及时剪枝（即当sum_>target之后就可以不用往下进行回溯了），并且可以使用一个累加的sum_代替掉使用内置的sum方法，节省时间开销。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        sum_ = 0

        def backtracking(startIndex, path):
            nonlocal sum_
            if sum_ > target:
                return
            if sum_ == target:
                res.append(path[:])
                return
            for i in range(startIndex, len(candidates)):
                path.append(candidates[i])
                sum_ += candidates[i]
                backtracking(i, path)
                sum_ -= path.pop()

        backtracking(0, [])
        return res

image-20231122222739974

40、组合总数II（*）

image-20231123110032934

本题需要注意的是，跟前面不同的地方在于每个数字在每个组合中只能使用一次，同时在解集中不能包含重复的组合。因此想到设置一个used数组来表示每个元素是否已经被访问过。 此处也可以不使用used数组

==其中candidates数组需要进行排序==，这样能够保证如果数字相同的情况下，只会使用一次。

40.组合总和II

要去重的是同一层上是否使用过，可以看出在candidates[i] == candidates[i - 1]相同的情况下：

  • used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
  • used[i - 1] == false，说明同一树层candidates[i - 1]使用过

40.组合总和II1

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []  # 用于记录返回结果
        sum_ = 0
        def backtracking(candidates,target,path,startindex,used):
            nonlocal sum_
            if sum_>target:
                return 
            if sum_==target:
                res.append(path[:])
                return 
            for i in range(startindex,len(candidates)):
                if i>startindex and candidates[i]==candidates[i-1] and not used[i-1]:
                    continue
                path.append(candidates[i])
                sum_+=candidates[i]
                used[i]=True
                backtracking(candidates,target,path,i+1,used)
                sum_-=candidates[i]
                used[i]=False
                path.pop()
        # candidates需要进行排序，否则相同的数字可能不会连续
        candidates.sort()
        backtracking(candidates,target,[],0,[False]*len(candidates))
        return res

image-20231123110223652

优化 + 不使用used数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []

        def backtracking(candidates,target,startindex,sum_,path):
            if sum_==target:
                res.append(path[:])
                return
            for i in range(startindex, len(candidates)):
                if i>startindex and candidates[i]==candidates[i-1]:
                    continue
                sum_+=candidates[i]
                # 这里进行判断，如果超过target则直接break 免去了后面的循环 节省时间开销	
                if sum_ > target:
                    break
                path.append(candidates[i])
                backtracking(candidates,target,i+1,sum_,path)
                sum_-=candidates[i]
                path.pop()
        candidates.sort()
        backtracking(candidates,target,0,0,[])
        return res

image-20231127100152702

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        sum_ = 0

        def backtracking(startIndex, path):
            nonlocal sum_
            if sum_ > target:
                return
            if sum_ == target:
                res.append(path[:])
                return
            for i in range(startIndex, len(candidates)):
                if i > startIndex and candidates[i] == candidates[i - 1]:
                    continue
                path.append(candidates[i])
                sum_ += candidates[i]
                backtracking(i + 1, path)
                sum_ -= path.pop()

        candidates.sort()
        backtracking(0, [])
        return res

131、分割回文串（*）

image-20231123151758868

本题递归结束的条件是当startindex==字符串s 的长度时，往结果集中添加数据并返回。

递归的参数是startindex，和path，需要进行递归的字符串为s[startindex:i+1]进行切片，同时本题要求是回文子串，所以还需要加上判断是否是回文数字，如果是回文数字才进行回溯，不是回文数字的话不进行任何操作。

在递归体部分，需要一个for循环，其遍历范围是startindex到len(s)，然后往path列表中添加的元素是s[startindex:i+1]，这里注意字符串的切片是左闭右开的，因此这里区间是i+1，然后递归进行遍历backtracking(s,i+1,path)，注意这里的startindex需要从i+1开始，这是因为根据题目的要求，不会有重复出现的子串。

在【39、组合总数】一题中，题目说明candidates中的元素是可以重复出现的，因此我们在进行递归的时候传入的startindex就为for循环遍历的层数i，这样就可以一直递归下去找到符合条件的答案。但是本题中不能出现重复的所以传入的参数是i+1

递归三要素

  • 参数和返回值
1
def backtracking(s, startindex, path):
  • 递归终止条件
1
2
3
if startindex==len(s):
    res.append(path[:])
    return
  • 递归体 单层搜索过程
1
2
3
4
5
for i in range(startindex,len(s)):
    if huiwen(s[startindex:i+1]):
        path.append(s[startindex:i+1])
        backtracking(s,i+1,path)
        path.pop()

全部代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        res = []
        def backtracking(s,startindex,path):
            # print(startindex)
            # 如果分割到字符串末尾，则该轮结束
            if len(s)==startindex:
                res.append(path[:])
            
            for i in range(startindex,len(s)):
                # print(s[startindex:i+1])
                # 如果不是回文子串 不往path中添加
                if huiwen(s[startindex:i+1]):
                    path.append(s[startindex:i+1])
                    backtracking(s,i+1,path)
                    path.pop()
        
        def huiwen(s):
            return True if s==s[::-1] else False
            # i = 0
            # j = len(s)-1
            # while i<j:
            #     if s[i]!=s[j]:
            #         return False
            #     i+=1
            #     j-=1
            # return True
        
        backtracking(s,0,[])
        return res

image-20231125170244551

93、复原IP地址（*）

image-20231123215751666

image-20231123215802814

本题与分割字符串有几分相似，也属于分割问题。

递归三要素

  • 递归参数

字符串s，startindex和pointNum

pointNum表示IP地址中的.，如果有三个.的话，就说明当前的IP地址已经被分成四段了。

  • 递归结束的条件

根据本题要求，只要我们当前的字符串已经被分割成四段，即pointNum==3的时候，往res列表中添加结果并返回

  • 单层递归体中的操作
1
2
3
4
5
6
7
8
for i in range(startindex, len(s)):
    # IP 地址合法性剪枝
    if isValid(s[startindex:i+1]):
        sub = s[startindex:i+1]
        # 这里不能直接修改 path，而是使用一个副本进行传参
        backtracking(i + 1, path + sub + ".", pointNum + 1)
        else:
            break

img

校验逻辑：

  • 每一段以0开头则不合法
  • 每一段有非正整数数字不合法
  • 每一段数字如果大于255则不合法
1
2
3
4
def isValid(s):
    if len(s) == 0 or (s[0] == "0" and len(s) > 1) or int(s) > 255:
        return False
    return True

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        res = []

        def backtracking(startindex, path, pointNum):
            # 长度剪枝
            if len(s) - startindex > (4 - pointNum) * 3:
                return
            if len(s) - startindex < (4 - pointNum):
                return
            
            if pointNum == 3:
                if isValid(s[startindex:]):
                    res.append(path + s[startindex:])
                return
            
            for i in range(startindex, len(s)):
                # IP 地址合法性剪枝
                if isValid(s[startindex:i+1]):
                    sub = s[startindex:i+1]
                    # 这里不能直接修改 path，而是使用一个副本进行传参
                    backtracking(i + 1, path + sub + ".", pointNum + 1)
                else:
                    break
                
        def isValid(s):
            if len(s) == 0 or (s[0] == "0" and len(s) > 1) or int(s) > 255:
                return False
            return True

        backtracking(0, "", 0)
        return res

78、子集

image-20231124100225029

思路：

如果把子集问题抽象成一颗树的话，组合问题和分割问题都是收集树的叶子结点，子集问题是找树的所有结点。

78.子集

子集是无序的，{1,2}和{2,1}是等价的，也就是说之前取过的元素后面不会再取，因此在递归的过程中还需要传递一个参数startindex，每次都是从startindex继续往后进行搜索，而不是从0开始，如果是排列问题的话，for循环就要从0开始了，因为在排列中{1,2}和{2,1}是两个不一样的排列。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        def backtracking(nums,startindex,path):
            res.append(path[:])
            # 这里不需要加递归结束的条件，当startindex达到len(nums)的时候程序也就自动返回了
            for i in range(startindex,len(nums)):
                path.append(nums[i])
                backtracking(nums,i+1,path)
                path.pop()
        backtracking(nums,0,[])
        return res

90、子集II（*）

image-20231124101803120

本题和上一题的区别在于nums数组中可能包含重复元素，我们首先将其进行==排序==，然后在往res列表中添加数据的时候，进行判断只有不在res列表中的结果才能添加进去。其余部分和上一题一样。

  • 使用in操作去重
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        # nums = list(set(nums))
        res = []

        def backtracking(nums, startindex, path):
            if path not in res:
                res.append(path[:])
            if startindex>len(nums):
                return
            for i in range(startindex,len(nums)):
                path.append(nums[i])
                backtracking(nums,i+1,path)
                path.pop()
        nums.sort()
        backtracking(nums,0,[])
        return res

本题是树层去重，在同一层重复出现的需要去除重复值；树层去重的话需要对数组进行排序。

90.子集II

  • 直接判断去重
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res = []

        def backtracking(startIndex, path):
            res.append(path[:])
            for i in range(startIndex, len(nums)):
                if i > startIndex and nums[i] == nums[i - 1]:
                    continue
                path.append(nums[i])
                backtracking(i + 1, path)
                path.pop()

        nums.sort()
        backtracking(0, [])
        return res
  • 使用==used数组==去重（推荐）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res = []
        used = [False]*len(nums)

        def backtracking(nums,startindex,path,used):
            res.append(path[:])
            if startindex > len(nums):
                return 
            for i in range(startindex,len(nums)):
                if i>0 and nums[i]==nums[i-1] and not used[i-1]:
                    continue
                used[i] = True
                path.append(nums[i])
                backtracking(nums,i+1,path,used)
                used[i] = False
                path.pop()
        nums.sort()
        backtracking(nums,0,[],used)
        return res

90.子集II

491、递增子序列（*）

image-20231124211319729

本题需要再输入的序列中找到全部的递增子序列，同时需要注意的是题目中输入的数组会包含重复的元素，并且说明如果出现两个整数相等也会看作是递增序列的一种特殊情况。

利用回溯的思路，我们写出递归的三要素：

  • 参数和返回值

参数有：startindex用于记录下一层遍历的起始位置； path 用于记录结果列表

1
def backtracking(startindex, path):
  • 递归终止条件

题目中要求递增子序列中至少2个元素，因此可以判断如果len(path)>1则往res列表中添加结果并返回

这里需要注意，不能加return，加上了return的话，就会导致同一个树枝上的其他结果不能得到保存，这点类似于子集问题，子集问题是需要寻找叶子上的节点。

1
2
3
if len(path)>1:
    res.append(path[:])
    # return
  • 单层搜索逻辑

本题需要寻找递增子序列，不像之前的题目可以直接通过排序解决去重问题，因此需要使用另一种去重的方式，使用python中的集合，在Python中集合也是一个哈希表，可以在O(1)时间复杂度查询到想要的结果。

这里注意条件是和递增是或者or的关系的，即如果该数字已经在uset中，说明已经使用过了，需要跳过该数字。

同时uset是在每一层都会重新进行定义的，uset只会负责本层的结果。同一个父节点下的一层内如果出现重复数字则直接跳过

这里的一层指的是节点拥有同一个父节点

491. 递增子序列1

1
2
3
4
5
6
7
8
uset = set()
for i in range(startindex, len(nums)):
    if (path and path[-1]>=nums[i]) or nums[i] in uset:
        continue
    uset.add(nums[i])
    path.append(nums[i])
    backtracking(nums,i+1,path)
    path.pop()

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        res = []

        def backtracking(startIndex, path):
            if len(path) > 1:
                res.append(path[:])
            uset = set()
            for i in range(startIndex, len(nums)):
                if (path and path[-1] > nums[i]) or nums[i] in uset:
                    continue
                uset.add(nums[i])
                path.append(nums[i])
                backtracking(i + 1, path)
                path.pop()

        backtracking(0, [])
        return res

image-20231124213406251

46、全排列

image-20231124214516935

全排列和组合问题、切割问题以及子集问题的区别就在于每次遍历都需要从0开始，而不是传进来的startindex，也就是说全排列问题中是不需要startindex的。

另外在之前的几种问题中，有几个我们传入参数不是i+1而是i的，这是因为题目中说明可以出现重复元素。如果要求是不能出现重复元素的话，只能传入i+1。

本题中因为下标都是从0开始进行遍历的，所以就需要记录哪些数字之前已经被使用过了，所以这里有两个方法：

  • 使用used数组进行记录
  • 使用uset集合进行记录

上面的这两种方法都需要在函数的参数中进行传递

递归三部曲

  • 参数和返回值
1
def backtracking(path,used):
  • 递归终止条件
1
2
3
if len(path)==len(nums):
    res.append(path[:])
    return
  • 单层搜索逻辑
1
2
3
4
5
6
7
8
for i in range(0, len(nums)):
    if used[i]:
    	continue
    used[i]=True
    path.append(nums[i])
    backtracking(nums,path)
    used[i]=False
    path.pop()

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        used = [False] * len(nums)

        def backtracking(path, used):
            if len(path) == len(nums):
                res.append(path[:])
                return
            for i in range(len(nums)):
                if used[i]:
                    continue
                used[i] = True
                path.append(nums[i])
                backtracking(path, used)
                path.pop()
                used[i] = False

        backtracking([], used)
        return res

image-20231125112358453

使用uset集合避免使用个重复的数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []

        def backtracking(path, uset):
            if len(path) == len(nums):
                res.append(path[:])
                return
            for i in range(len(nums)):
                if nums[i] in uset:
                    continue
                uset.add(nums[i])
                path.append(nums[i])
                backtracking(path, uset)
                uset.remove(path.pop())

        backtracking([], set())
        return res

image-20240319092628141

47、全排列II（*）

image-20231124215605773

本题因为nums中包含重复的数字，因此需要去重，去重的时候因为需要判断相邻的两个数是否相等，所以在一开始需要对nums进行排序。【排序和重复数字去重是一个配套操作需要一起来】

之后本题的和全排列的区别就在于需要判断相邻的两数是否相等并且前一个数是否没有用过。

for循环是横向遍历，递归是纵向遍历（即沿着树枝进行遍历的效果）

img

used数组主要使用来记录哪些元素已经使用过了，全排列问题中元素不能重复使用，每个元素都只能适用一次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res = []

        def backtracking(path, used):
            if len(path) == len(nums):
                res.append(path[:])
                return

            for i in range(len(nums)):
                if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                    continue
                if used[i]:
                    continue
                path.append(nums[i])
                used[i] = True
                backtracking(path, used)
                path.pop()
                used[i] = False

        nums.sort()
        backtracking([], [False] * len(nums))
        return res

组合问题和排列问题是在树形结构的叶子结点上收集结果，而子集问题就是取树上所有结点的结果。

and not used[i - 1]这部分代码是用来跳过重复的数字，如果前一个数字没有被选取，并且和当前数字值一致，则可以跳过这部分，这样的操作可以避免答案中出现重复的值。

使用uesd数组进行去重：
img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res = []
        used = [False] * len(nums)

        def backtracking(path, used):
            if len(path) == len(nums):
                res.append(path[:])
                return

            for i in range(len(nums)):
                if i>0 and nums[i]==nums[i-1] and not used[i-1]:
                    continue
                if used[i]:
                    continue
                used[i] = True
                path.append(nums[i])
                backtracking(path, used)
                used[i] = False
                path.pop()

        nums.sort()
        backtracking([], used)
        return res

image-20231125112843814

784、字母大小写全排列

322、重新安排行程（hard)

image-20231127103728274

51、N皇后

image-20231127111457348

递归参数

定义res来存放最终的结果，n棋盘大小，row记录当前遍历到棋盘的第几层

1

递归终止条件

51.N皇后

当递归到叶子结点的时候就可以收集结果了。

1
2
3
if row==n:
    res.append(chessboard)
    return ;

单层递归逻辑

遍历这个棋盘的每一行，在python中，二维数组的表示就用嵌套列表表示即可。

验证棋盘是否合法

  • 皇后不能同行
  • 皇后不能同列
  • 皇后不能斜对角线（45度和135度）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def isValid(row, col, chessboard):
            # 列检查
            for i in range(row):
                if chessboard[i][col] == "Q":
                    return False
            # 45°角检查 这里的检查是从row col往前找
            i,j = row-1,col-1
            while i>=0 and j>=0:
                if chessboard[i][j] == "Q":
                    return False
                i-=1
                j-=1
            
            # 135°角检查
            i,j = row-1, col+1
            while i>=0 and j<len(chessboard):
                if chessboard[i][j]=="Q":
                    return False
                i -= 1
                j += 1
            return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:    
        def backtracking(n,row,chessboard):
            # 递归终止的条件 当递归参数row==n时就进行发返回 并将结果添加到res中
            if row==n:
                res.append(chessboard[:])
                return
            # 对棋盘的每一行进行操作 判断是否合法
            for col in range(n):
                if isValid(row,col,chessboard):
                    chessboard[row] = chessboard[row][:col] + "Q" + chessboard[row][col+1:]
                    backtracking(n,row+1,chessboard)
                    chessboard[row] = chessboard[row][:col] + "." + chessboard[row][col+1:]
        
        def isValid(row, col, chessboard):
            # 列检查
            for i in range(row):
                if chessboard[i][col] == "Q":
                    return False
            # 45°角检查 这里的检查是从row col往前找
            i,j = row-1,col-1
            while i>=0 and j>=0:
                if chessboard[i][j] == "Q":
                    return False
                i-=1
                j-=1
            
            # 135°角检查
            i,j = row-1, col+1
            while i>=0 and j<len(chessboard):
                if chessboard[i][j]=="Q":
                    return False
                i -= 1
                j += 1
            

            return True
        
        res = []
        chessboard = ["."*n for _ in range(n) ]
        print(chessboard)
        backtracking(n,0,chessboard)
        return res

解数独

回溯总结

需要startIndex的题目有：

需要return的情况有：

一般情况下，如果题目中要求不能出现重复的数据，需要搭配这used数组进行使用，除此之外还需要对集合进行一个排序，这样可以在值相同的情况下进行判断。

1
2
if i>0 and nums[i]==nums[i-1] and not used[i-1]:
    continue

used[i-1]==False 说明在同一层的前面结点已经使用过该数据了，后面不需要重复进行操作。

如果集合中存在重复的数字序列，则需要对其进行排序

  • 组合总数II
  • 子集II
  • 全排列II