刷了一天回溯算法

由于发现自己递归的回溯部分还是不太清楚，今天就特意抽出一整天的时间来练习回溯算法。

练习方式：把《代码随想录》上面第九章回溯算法这一章的所有题目，总共有十四道题目都做了一遍。

32 分钟前 #37 解数独 困难 2 次
4 小时前 #51 N 皇后 困难 3 次
5 小时前 #47 全排列 II 中等 1 次
5 小时前 #46 全排列 中等 1 次
5 小时前 #491 递增子序列 中等 3 次
7 小时前 #90 子集 II 中等 3 次
8 小时前 #78 子集 中等 1 次
8 小时前 #93 复原 IP 地址 中等 1 次
8 小时前 #131 分割回文串 中等 1 次
10 小时前 #40 组合总和 II 中等 4 次
11 小时前 #39 组合总和 中等 1 次
12 小时前 #17 电话号码的字母组合 中等 2 次
12 小时前 #216 组合总和 III 中等 1 次
12 小时前 #77 组合 中等 2 次

回顾复盘一下

77. 组合

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

        def dfs(left: int, lst: list, remain: int):
            if remain == 0:
                res.append(lst[:])
                return

            if left > n:
                return

            for i in range(left, n + 1):
                lst.append(i)
                dfs(i + 1, lst, remain - 1)
                lst.pop()  # 精髓，撤销！！

        dfs(1, [], k)
        return res

这个题以前是直接用python的combination做的，但是总感觉用库心里不踏实，没有学到精髓。也不利于递归思维的提升。所以就看书学了学回溯算法。

感觉回溯算法的核心精髓，就是：每次递归操作完了之后都会撤销当前操作。，就比如这段代码里面的 lst.pop()，忽然感觉以前的自己实在是太屑了。不知道在遍历决策树的时候怎么倒退，干着急也没办法，原来就是这么简单，感觉很妙。

216. 组合总和 III

1
2
3
4
5
6
7
from itertools import combinations


class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        return [list(item) for item in combinations(range(1, 10), k) if sum(item) == n]

这个题偷了个懒。感觉和第一题有点相似了。就调了个库

17. 电话号码的字母组合

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 letterCombinations(self, digits: str) -> List[str]:
        res = []
        if digits == "":
            return res
        digs = [
            "abc",
            "def",
            "ghi",
            "jkl",
            "mno",
            "pqrs",
            "tuv",
            "wxyz",
        ]

        def dfs(digIndex: int, path: str):
            # digIndex：表示当前选到了第几个数字
            # path，写入答案的暂存小数组
            if digIndex >= len(digits):
                res.append(path)
                return

            for char in digs[int(digits[digIndex]) - 2]:  # 这里稍微绕了一下的就是把数字转化成索引，-2
                # 树形宽度遍历每一种字符可能
                path += char
                dfs(digIndex + 1, path)
                path = path[:-1]  # 去掉最后一个字符，用的切片
            ...

        dfs(0, "")
        return res

这个题踩了个坑WA了一下，传入空字符串的时候居然回出错，于是就加了个特殊判断。

这个题目看了之后梦回小学时代，那个时候我还在用诺基亚。题目就是用一个九键手机，给出一串数字，给出所有的能匹配出来的字母，这个题好像和实际的现实还不太一样，因为现实情况实际上是想打出一个b，要按两下2才行。这个只是直接求组合的所有可能了。就是按一下2，abc都有可能了。

想起来以前周赛好像做过一个题，是给出了很长很长一串数字，问可能打出多少种字母，那个题的配图和这个题的配图居然是一样的我记得。但是这个题好像感觉不如那个题难，那个题当时是用动态规划来解决的。当时居然还做了快一个小时，当时那个题的dp递推式子居然是刚好碰出来的。

39. 组合总和

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 combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []

        def dfs(left: int, sumVal: int, path: List[int]):
            # left 当前要选择的数组的下标
            # sumval 当前已经选择了的和
            # path 当前选择了的数字 list
            if sumVal > target:
                # 如果已经选超了，就不要再选下去了
                return
            if sumVal == target:
                # 刚好！记录答案
                res.append(path[:])
                return
            # sum 还不够
            for i in range(left, len(candidates)):
                path.append(candidates[i])  # 添加一个当前这个数字
                dfs(i, sumVal + candidates[i], path)  # 第一个参数i不用加1.因为可以无限选择
                path.pop()  # 撤销
            ...

        dfs(0, 0, [])
        return res

这个题不一样的点在于里面的元素可以无限次被选择。

做到这道题的时候就感觉自己在22年五月份还是四月份的时候，也就是刷剑指offer1的时候，自己当时的很多这种组合问题好像也遇到过，当时就是全用的combination全偷懒做的，一遇到变种，发现不能偷懒，就不会了，当时就直接抄别人的答案提交了。但是打开这道题的时候找不到自己的提交记录了，可能是剑指offer上面的题有重复的一样的题，题源地址可能不是一个。

40. 组合总和 II

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:
    # 2022年6月16日
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        res = []

        def dfs(left: int, sumVal: int, path: list):
            if sumVal > target:
                # 已经加超过了
                # print("add over")
                return
            if sumVal == target:
                # 刚好
                res.append(path[:])
            if sumVal < target:
                # 继续递归
                s = set()
                for i in range(left + 1, len(candidates)):

                    addNum = candidates[i]
                    if addNum in s:
                        continue
                    s.add(addNum)

                    path.append(addNum)
                    dfs(i, sumVal + addNum, path)
                    path.pop()

        dfs(-1, 0, [])  # 从-1开始，因为for循环遍历会+1，就加成0了
        return res

这个题总是超过时间限制

这个题的特点是：结果的每一个组合里可以有重复的数字，但是！！所有的结果里不能有重复的组合。。。

就是有一个组合 [1, 1, 2] 是合法的，但是不能有两个 [1, 1, 2]。

这个我和书上的最开始的做法很一致，一上来先拍了序，但是排序之后怎么去重是个大问题，最开始我是直接遍历所有组合，单纯用一个集合放在最外层来去重，但是发现这样总是超时。

其实应该是在遍历决策树的时候，直接用同层重复数字来剪枝去重，不仅达到了去重的效果，而且还达到大大大大节省时间的效果。

这里的同层去重就是在内层放一个set，就是刚好在for的外一层的地方。然后先检测是否在集合里就行了。

131. 分割回文串

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
def test(a: str):
    return a == a[::-1]


class Solution:
    def partition(self, s: str) -> List[List[str]]:
        res = []

        def dfs(remain: str, path: list):
            # print(path)
            if not remain:
                return
            if test(remain):
                res.append(path[:] + [remain])
            for i in range(len(remain)):
                # 在当前位置i一切割
                left = remain[:i + 1]
                if not test(left):
                    continue
                right = remain[i + 1:]
                # print("/t", path, left, right)
                path.append(left)
                dfs(right, path)
                path.pop()

        dfs(s, [])
        return res

判断一个字符串是不是回文的，直接用python语法糖了。本质上都是用的线性的时间复杂度。

这个题问的意思是，在一个字符串的各个缝隙位置上放若干个隔板，隔板分割出来的每一个字符串都是回文的。

有多少种放隔板的方式。

我规定的下标是在对应i下标元素之后，与i+1之间放隔板。

想了想执行一次之后就通过了

93. 复原 IP 地址

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
class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        res = []

        def dfs(remain: str, path: list):
            if len(path) == 4 and not remain:
                # 没有剩余的了，并且path刚好也等于四，记录答案！
                res.append(".".join(path))
            if len(path) == 4 and remain:
                # 已经满了但是还没切完呢
                return
            for i in range(min(3, len(remain))):
                if remain[0] == "0":  # 因为不能有前导零，所以加个图书判断
                    path.append("0")
                    dfs(remain[1:], path)
                    path.pop()
                    break
                # 遍历每一个剩余可切割索引
                leftStr = remain[:i + 1]
                rightStr = remain[i + 1:]
                if int(leftStr) < 256:
                    path.append(leftStr)
                    dfs(rightStr, path)
                    path.pop()
                ...
        dfs(s, [])
        return res

这个题是把所有可能的IP地址返回出来，就是不停的加点，和上一个题有点像。

这个题里面有一些特殊情况的处理。

78. 子集

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

        def dfs(left: int, path: list):
            if left >= len(nums):
                res.append(path[:])
                return

            # 我要当前这个
            path.append(nums[left])
            dfs(left + 1, path)
            path.pop()
            # 我不要当前这个
            dfs(left + 1, path)
            ...

        dfs(0, [])
        return res

这题就是获取一个集合的幂集，以前做这个题的时候我发现自己是用combination偷懒了。这次好好做一下。

这个做的时候懵了一下，看了一下书上画的图才意识到，原来是在决策树上每走一步都记录添加。

这个不是for循环横向扩展决策树宽度了。而是一个二叉树的形状，要不要当前位置了。

90. 子集 II

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
class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()

        def dfs(left: int, path: list):
            if left >= len(nums):
                return
            s = set()
            for i in range(left + 1, len(nums)):
                # 要
                n = nums[i]
                if n in s:
                    continue
                else:
                    s.add(n)
                path.append(n)
                res.append(path[:])
                dfs(i, path)
                path.pop()
                ...
            ...

        dfs(-1, [])  # 又是从-1开始

        return res + [[]]

这个题是变成了集合里有重复元素了，然后返回幂集。

答案里面可以有 [1, 1, 2] 这样的子集，但是不能有重复的子集，就不能有两个[1, 1, 2]。这又成了去重问题了

这个去重问题也是，先排序，然后再对决策树同层去重。

491. 递增子序列

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
class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        res = []

        def dfs(left: int, path: list):
            s = set()
            if len(path) >= 2:
                res.append(path[:])
            for i in range(left + 1, len(nums)):

                n = nums[i]
                if n not in s:
                    s.add(n)
                else:
                    continue
                if path and path[-1] > n:
                    continue
                path.append(n)
                dfs(i, path)

                path.pop()
            ...

        dfs(-1, [])  # 在for循环里才开始选择，会+1，所以写了-1
        # print(len(res))
        return res

这个题目就如题的名字一样简洁，获得一个数组的所有的递增的子序列。因为递增性质，所以所有子序列的长度必须是大于等于2的。

这个题也是，发现得去重，去重就挺麻烦的，发现是同层去重。

然后记录答案的时候，是只要path数组的长度一旦大于2，就会记录。

最开始看到这个题我想的是，这不直接来个二重循环就可以了吗。后来逝了一下才发现，不行。因为二重循环里面那一层没法做到间断跳跃的选择。这个题WA了两次。边界条件还得处理。

46. 全排列

这个题好像也可以直接调用itertools里面的全排列直接写，但是就失去练习的意义了。所以特意要学习一下回溯怎么实现全排列。

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

        def dfs(path: list):
            if len(path) == len(nums):
                res.append([nums[i] for i in path])

            for i in range(len(nums)):
                if i in path:  # 排除自己选自己
                    continue
                path.append(i)
                dfs(path)
                path.pop()

        dfs([])
        return res

这个决策树就是一个完整的树了，像之前的题一样，左边深右边空。

记录答案的时候就刚好是path数组写满了的时候就记录。

for循环里面写的也是，直接遍历满，要排除自己。

以前大二的时候刚做行列式的程序就用到了全排列算法，当时自己不知道python内置库实现了，就自己瞎搞，搞的代码又臭又长，空间复杂度On！，直接生成了一个多叉树，也根本不会回溯，就无奈又把多叉树改成了三叉链表。增加了指向父亲节点的指针。特别特别麻烦，居然还搞了一下午。现在看看以前的自己真的好憨憨。但也没办法。只是感觉过去的自己学习的进度和效率低了。

现在看看这个全排列算法，感觉不怎么难。看着这么几行代码，居然还感觉有点简单。

也许我应该有这样一个警醒：当我特别想做出一个东西，但是我的算法卡脖子了，然后我硬是去用自己的方法做。虽然可能很有成就感，但是这可能说明我的算法技能和知识有着严重漏洞。

47. 全排列 II

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 dfs(choice: list, path: list):
            if len(nums) == len(path):
                res.append(path[:])

            s = set()
            for i in range(len(nums)):
                if i in choice or nums[i] in s:
                    continue
                s.add(nums[i])
                # 选择这个元素
                choice.append(i)
                path.append(nums[i])
                dfs(choice, path)
                path.pop()
                choice.pop()
            ...

        dfs([], [])
        return res

这个题就是在上一个题的基础上，要给出全排列的序列里面有了重复的元素了。

这个去重又有点麻烦了。搞了挺长时间。

递归参数搞了两个数组，一个是记录选择下标的数组，一个是记录选择的元素的数组，

选择下标的数组不能重复选择，选择元素的数组在树的同层也是要去重的。

51. N 皇后

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
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        res = []

        def dfs(lines: list, y: int):
            if len(lines) == n:
                # write
                # print(lines, y)
                ans = []
                for x in lines:
                    line = ["."] * n
                    line[x] = "Q"
                    ans.append("".join(line))
                res.append(ans)
                return
            if y >= n:
                return
            for x in range(n):
                # 判断竖着是否重复
                if x in lines:
                    continue
                # 判断斜着是否重复
                lst = []
                for i, q in enumerate(lines):
                    lst.extend((q - (y - i), q + (y - i)))
                # print("/t", lines, lst)
                if x in lst:
                    continue
                # 这个位置可以放
                lines.append(x)
                dfs(lines, y + 1)
                lines.pop()
            ...

        dfs([], 0)
        return res

这个N皇后问题，以前做过，一看提交记录发现，竟然恰好是上一年的这个月

提交结果 执行用时 内存消耗 语言 提交时间 备注
通过 72 ms 15.3 MB Python3 2022/06/16 17:10
添加备注
通过 996 ms 15.8 MB Python3 2021/06/13 18:03
DFS，减少了搜索范围
超出时间限制 N/A N/A Python3 2021/06/13 16:26

上一年的今天左右相差了三天，回忆起以前这个题当时搞了好像将近两个多小时，这次好像半小时就搞过了。看来掌握回溯就是好啊。

并且当时的运行时间也好多。

现在写的时候，就判断斜着相撞的时候，绕了一下。

字符串处理也感觉得心应手了。

37. 解数独

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
def valid(board: List[List[str]]) -> bool:
    # line
    for line in board:
        for char in line:
            if char == ".":
                continue
            if line.count(char) > 1:
                return False
    # col
    for x in range(9):
        s = set()
        for y in range(9):
            char = board[y][x]
            if char == ".":
                continue
            if char in s:
                return False
            s.add(char)
    # box
    for y in range(3):
        locY = y * 3

        for x in range(3):
            locX = x * 3

            s = set()
            for dy in range(3):
                realY = locY + dy
                for dx in range(3):
                    realX = locX + dx
                    char = board[realY][realX]
                    if char == ".":
                        continue
                    if char in s:
                        return False
                    s.add(char)
    return True


def full(board: List[List[str]]):
    for line in board:
        for char in line:
            if char == ".":
                return False
    return True


class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        # 记录下来所有可以更改的坐标点
        modifyList = []  # len = 51
        for y, line in enumerate(board):
            modifyList.extend((x, y) for x, char in enumerate(line) if char == ".")
        success = False

        # 在所有可以更改的坐标点上一步一步往前实验
        # 每试一次就全局检测一次，如果检测失败就往回反

        def dfs(modifyIndex: int):
            nonlocal success
            if success:
                return
            if not valid(board):
                return
            if modifyIndex >= len(modifyList):
                success = True
                return

            mx, my = modifyList[modifyIndex]
            for i in range(1, 10):
                board[my][mx] = str(i)
                dfs(modifyIndex + 1)
                if not success:
                    board[my][mx] = "."
                else:
                    break

        dfs(0)

这个解数独，以前大一的时候2020年上半年，也就是刚开始学python的那半年搞出来过，当时还没学算法，还没学数据结构，就是想搞出来解决数独的问题。当时也还做了框图。只是没有用递归。做了整整大半天。

后来知道了leetcode，发现了有解数独这个题，只是没想到格式居然是字符串格式，太麻烦了，就一直没做。

今天终于把这个题给解决了。

判断数独整体是否有效的时候还是出了点小bug。

整个回溯递归的时候逻辑也遇到了点问题，发现自己明明写好了，但是最后好像又全给擦掉了，就用了一个success变量。但是又发现最后填写的数全都变成9了，原来是自己在递归for循环里忘了break了。还是有好多小细节问题。

总结

今天用了整整一天的时间又弥补了一下以前算法一直欠缺的地方，感觉很有收获。

这些去重的问题，层间去重和树枝下去重，书里讲的真的挺清楚的。这个书里给出的做题顺序也真的不错。

可能以后有时间还是要回头继续做这些题，时间长了可能又会变得生疏。也许一年之后，我又会变成一个更强的自己。回头看到自己现在写的代码可能还是不够好。