算法通关村第十八关：白银挑战-回溯热门问题

白银挑战-回溯热门问题

回溯主要解决一些暴力枚举也搞不定的问题zh，例如组合、分割、子集、排列、棋盘等。

1. 组合总和问题

LeetCode39
https://leetcode.cn/problems/combination-sum/

思路分析

如果不考虑重复，跟题目 LeetCode 113 类似
考虑重复的话，需要重新分析

对于序列{2,3,6,7}, target_sum=7

先选择1个2，剩下target=7-2=5
再选择1个2，剩下target=7-2-2=3
再选择1个2，剩下target=7-2-2-2=1，小于列表中最小的数2，不满足要求了

回退只选2个2时，target=7-2-2=3，序列{2,3,6,7}中有3，满足要求，{2,2,3}
回退只选1个2时，target=7-2=5，这时候不能选择2，从序列{3,6,7}中选择，没有符号要求的

依次类推，后面尝试从3、6、7开始选择，如图所示
图的横向是针对每个元素的暴力枚举，纵向是递归

代码实现

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(path, nums, start_index, target):
            if target < 0:
                return
            if target == 0 and path:
                res.append(path[:])
                return
            for i in range(start_index, len(nums)):
                if nums[i] <= target:
                    path.append(nums[i])
                    dfs(path, nums, i, target - nums[i])
                    path.pop()

        candidates.sort()
        res = []
        path = []
        dfs(path, candidates, 0, target)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(path, start):
            if path and sum(path) > target:
                return
            if path and sum(path) == target:
                res.append(path[:])
                return

            for i in range(start, len(candidates)):
                path.append(candidates[i])
                dfs(path, i)
                path.pop()

        candidates.sort()
        res = []
        dfs([], 0)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

题目拓展

如果输入的 candidates 数组中存在负数怎么办，如何实现呢？

2. 分割回文串

分割问题也是回溯要解决的典型题目之一，常见的题目有分割回文串，分割IP地址、以及分割字符串等

LeetCode131 分割回文串
https://leetcode.cn/problems/palindrome-partitioning/

思路分析

本题包含两个点：

1. 如何判断回文串？=> 双指针
2. 如何切割？=> 回溯

暴力切割，非常困难，使用回溯就简单清晰的多

• 试一试，第一次切’a’，第二次切’aa’，第三次切’b’，对应的回溯里的for循环，横向
• 第一次切了’a’，剩下’ab’。进行递归继续切割’ab’，对应纵向
• 切割线切割到字符串的结尾位置，说明找到了一个切割方法

代码实现

class Solution:
    def __init__(self):
        self.res = []
        self.path = []
        
    # 判断回文串
    def is_palindrome(self, str):
        start, end = 0, len(str) - 1
        while start < end:
            if str[start] != str[end]:
                return False
            start += 1
            end -= 1
        return True

    # 回溯
    def backtracking(self, start_index, s):
        if self.path and start_index > len(s) - 1:
            self.res.append(self.path[:])
            return

        for i in range(start_index, len(s)):
            # 判断是否为回文串
            child_str = s[start_index:i + 1]
            if self.is_palindrome(child_str):
                self.path.append(child_str)
                self.backtracking(i + 1, s) # 递归纵向遍历，判断其余是否是回文串
                self.path.pop() # 回溯

    def partition(self, s: str) -> List[List[str]]:
        if not s:
            return []
        self.backtracking(0, s)
        return self.res
        
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

3. 子集问题

子集问题，回溯的经典使用场景。
回溯可以化成一种树状结构，子集、组合、分割问题都可以抽象为一棵树
子集问题与其他类型相比有个明显的区别，组合问题一般找到满足要求的结果即可，而集合则要找出所有的情况

LeetCode 78 子集
https://leetcode.cn/problems/subsets/

思路分析

递归停止条件
什么时候停下来？起始可以不加终止条件，因为 start_index >= nums.size()，本层for循环本来就结束了。
求取子集问题，不需要任何剪枝！子集就是要遍历整棵树

例子：分析 [1,2,3] 的子集

代码实现

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def dfs(start_index, path):
            res.append(path[:])
            # 终止条件加不加都行
            if start_index >= len(nums):
                return
            for i in range(start_index, len(nums)):
                path.append(nums[i])
                dfs(i + 1, path)
                path.pop()

        res = []
        path = []
        dfs(0, path)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

4. 排列问题

LeetCode 46
https://leetcode.cn/problems/permutations/

思路分析

这个问题与前面组合等问题的一个区别是使用过的后面还要在用，如[1,2]和[2,1]，从集合的角度看是一个，从排列的角度看是两个

元素1在[1,2]中已经使用过了，但是在[2,1]中还要再使用一次，所以就不能用start_index，为此可以使用一个used数组来标记已经选择的元素

终止条件的判断：收集元素的数组path的大小和nums数组一样大的时候，说明找到了一个全排列，表示到达了叶子结点

代码实现

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def dfs(path):
            if len(path) == len(nums):
                res.append(path[:])

            for i in nums:
                # 如果i已经被path收录，跳过
                if i not in path:
                    path.append(i)
                    dfs(path)
                    path.pop()

        res = []
        path = []
        dfs(path)
        return res
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]]:
        def dfs(path, used):
            if len(path) == len(nums):
                res.append(path[:])
            for i in range(len(nums)):
                if used[i]:
                    continue
                used[i] = True
                path.append(nums[i])
                dfs(path, used)
                path.pop()
                used[i] = False

        res = []
        path = []
        used = [False] * len(nums)
        dfs(path, used)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

5. 字母大小写全排列

LeetCode 784
https://leetcode.cn/problems/letter-case-permutation/

思路分析

这里的数字是干扰项，我们需要做的是过滤掉数字，只处理字母。另外还要添加个大小写转换的方法

由于每个字符的大小写形式刚好差了32，u因此在大小写转换时可以用加减32来进行转换和恢复

有点类似于上面的子集问题，多了一个判断是字母的处理

代码实现

class Solution:
    def letterCasePermutation(self, s: str) -> List[str]:
        def dfs(s_list, index):
            ans.append(''.join(s_list))
            # 此处递归终止条件可有可无
            if index >= len(s_list):
                return
            for i in range(index, len(s_list)):
                if s_list[i].isalpha():
                    s_list[i] = s_list[i].swapcase()
                    dfs(s_list, i + 1)
                    s_list[i] = s_list[i].swapcase()

        ans = []
        dfs(list(s), 0)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

另一种回溯的写法

class Solution:
    def letterCasePermutation(self, s: str) -> List[str]:
        def dfs(s_list, pos):
            while pos < len(s_list) and s_list[pos].isdigit():
                pos+=1
            if pos == len(s_list):
                res.append("".join(s_list))
                return
            
            s_list[pos] = s_list[pos].swapcase()
            dfs(s_list, pos+1)
            s_list[pos] = s_list[pos].swapcase()
            dfs(s_list, pos+1)
            
        res = []
        dfs(list(s), 0)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

6. 单词搜索

LeetCode 79
https://leetcode.cn/problems/word-search/

思路分析

从上到下，从做到右遍历网络，每个坐标递归调用 check(i,j,k) 函数，其中i,j表示网格坐标，k表示word中的第k个字符。
如果能搜索到第k个字符，返回true，否则返回false。

check(i,j,k)执行情况分析

• 坐标为 i,j 的字符和word中的第k个字符不相等，这条路径搜索失败，返回false
• 如果搜索到了字符串的结尾，则找到了网格中的一条路径，这条路径正好可以组成字符串s

以上两种情况都不满足，把当前网络节点加入 visited 数组，表示节点已经访问过了
然后顺着当前网络坐标的四个方向继续尝试

注：python二维数组的初始化方法

used = [[False for _ in range(len(board[0]))] for _ in range(len(board))]
1

代码实现

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(i, j, k, used):
            if not 0 <= i < len(board) or not 0 <= j < len(board[0]) or board[i][j] != word[k] or used[i][j]:
                return False
            if k == len(word) - 1:
                return True
            used[i][j] = True
            ans = dfs(i + 1, j, k + 1, used) or \
                  dfs(i - 1, j, k + 1, used) or \
                  dfs(i, j + 1, k + 1, used) or \
                  dfs(i, j - 1, k + 1, used)
            used[i][j] = False
            return ans

        used = [[False for _ in range(len(board[0]))] for _ in range(len(board))]
        for i in range(len(board)):
            for j in range(len(board[0])):
                if dfs(i, j, 0, used):
                    return True
        return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(i, j, k):
            if not 0 <= i < len(board) or not 0 <= j < len(board[0]) or board[i][j] != word[k]:
                return False
            if k == len(word) - 1:
                return True
            board[i][j] = ""
            ans = dfs(i + 1, j, k + 1) or \
                  dfs(i - 1, j, k + 1) or \
                  dfs(i, j + 1, k + 1) or \
                  dfs(i, j - 1, k + 1)
            board[i][j] = word[k]
            return ans

        for i in range(len(board)):
            for j in range(len(board[0])):
                if dfs(i, j, 0):
                    return True
        return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20