算法工程师的日常
0%

递归

发表于 更新于 分类于 ，

递归题目

递归

括号生成[22]

题目见 https://leetcode-cn.com/problems/generate-parentheses/, 就是用到递归的方法。
解法代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        cur = ""
        def dfs(left, right, cur):
            if left==0 and right==0:
                res.append(cur)
                return
            if left>right:
                return
            if left>0: # 注意
                dfs(left-1,right,cur+"(")
            if right>0:
                dfs(left, right-1,cur+")")
        dfs(n,n,cur)
        return 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
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def generate(A):
            if len(A) == 2*n:
                if valid(A):
                    ans.append("".join(A))
            else:
                A.append('(')
                generate(A)
                A.pop()
                A.append(')')
                generate(A)
                A.pop()

        def valid(A):
            bal = 0
            for c in A:
                if c == '(': bal += 1
                else: bal -= 1
                if bal < 0: return False
            return bal == 0

        ans = []
        generate([])
        return ans

可以看到代码比较狂野，就是啥都没判断，就直接append，然后pop，最后再去判断。
那么久可以优化一下了。

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

        def back(state, left, right):
            if left == 0 and right == 0:
                res.append("".join(state[:]))
                return
            if left > right:
                return
            if left > 0:
                state.append("(")
                back(state, left - 1, right)
                state.pop()
            if right > 0:
                state.append(")")
                back(state, left, right - 1)
                state.pop()

        back([], n, n)
        
        return res

整数替换[397]

题目见 https://leetcode-cn.com/problems/integer-replacement/ 这里考虑用动态规划，但是无法写出整体的转移方程，递归的做法如下：

1
2
3
4
5
6
7
8
9
10
class Solution:
    def integerReplacement(self, n: int) -> int:
        def helper(n):
            if n == 1: return 0
            if n % 2 == 0:
                return 1 + helper(n/2)
            else:
                return 1 + min(helper(n+1),helper(n-1))
        
        return helper(n)

分割数组为连续子序列[659]

自己写的超时了

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 isPossible(self, nums: List[int]) -> bool:
        def if_increase(nums2):
            if len(nums2)<3:
                return False
            for i in range(len(nums2)-1):
                if not nums2[i+1] - nums2[i]==1:
                    return False
            return True
        if if_increase(nums):
            return True
        for lens in range(3, len(nums)):
            left = []
            right = []
            for i in nums:
                if not left or i - left[-1] == 1 and len(left) < lens:
                    left.append(i)
                else:
                    right.append(i)
            if self.isPossible(left) and self.isPossible(right):
                return True
        return False

别人写的非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def isPossible(self, nums: List[int]) -> bool:
        counter = Counter(nums)
        tail = Counter()
        for i in nums:
            if counter[i] and tail[i - 1]:  # 可以衔接
                counter[i] -= 1
                tail[i - 1] -= 1
                tail[i] += 1
                continue
            if counter[i] and counter[i + 1] and counter[i + 2]:  # 可以生成新序列
                tail[i + 2] += 1
                counter[i] -= 1
                counter[i + 1] -= 1
                counter[i + 2] -= 1
                continue
        for k, v in counter.items():
            if v > 0:
                return False
        return True

来自 https://leetcode.cn/problems/split-array-into-consecutive-subsequences/description/

目标和[494]

代码如下，会超时

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 findTargetSumWays(self, nums: List[int], target: int) -> int:
        sets = set()

        def back(state, s, index):
            if len(state) == len(nums):
                if s == target:
                    if "".join(state) not in sets:
                        sets.add("".join(state[:]))
                        return
                    return
            for i in range(index, len(nums)):
                state.append("+1")
                s = s + nums[i]
                back(state, s, i + 1)
                s = s - nums[i]
                state.pop()

                s = s - nums[i]
                state.append("-1")
                back(state, s, i + 1)
                s = s + nums[i]
                state.pop()

        back([], 0, 0)
        sums = len(sets)
        return sums

其实是需要动态规划的。

回溯

模板

关于模板可以参考知乎这里
https://zhuanlan.zhihu.com/p/112926891

下面对其中说的好的部分进行说明（哈哈，就是直接复制过来方便自己看）。后面会总结自己的模板。

按照文章中所说的，大概的思路如下
直接给出设计思路
全局变量： 保存结果
参数设计： 递归函数的参数，是将上一次操作的合法状态当作下一次操作的初始位置。这里的参数，我理解为两种参数：状态变量和条件变量。（1）状态变量（state）就是最后结果（result）要保存的值；（2）条件变量就是决定搜索是否完毕或者合法的值。
完成条件： 完成条件是决定 状态变量和条件变量 在取什么值时可以判定整个搜索流程结束。搜索流程结束有两种含义： 搜索成功并保存结果 和 搜索失败并返回上一次状态。
递归过程： 传递当前状态给下一次递归进行搜索。

大概的代码上的逻辑是如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
res = []    # 定义全局变量保存最终结果
state = []  # 定义状态变量保存当前状态
p,q,r       # 定义条件变量（一般条件变量就是题目直接给的参数）
def back(状态，条件1，条件2，……):
    if # 不满足合法条件（可以说是剪枝）
        return
    elif # 状态满足最终要求
        res.append(state)   # 加入结果
        return 
    # 主要递归过程，一般是带有 循环体 或者 条件体
    for # 满足执行条件
    if  # 满足执行条件
        back(状态，条件1，条件2，……)
back(状态，条件1，条件2，……)
return res

个人感觉这个写的以很好了，不过可以稍微改进下，让它更容易被看懂

res = []    # 定义全局变量保存最终结果
state = []  # 定义状态变量保存当前状态
p,q,r       # 定义条件变量（一般条件变量就是题目直接给的参数）
def back(状态，条件1，条件2，……):
    if # 不满足合法条件（可以说是剪枝）
        return
    elif # 状态满足最终要求
        res.append(state)   # 加入结果
        return 
    # 主要递归过程，一般是带有 循环体 或者 条件体
    for # 满足执行条件
    if  # 满足执行条件
        状态+值 # 比如stata.append(xx)
        back(状态，条件1，条件2，……)
        状态-值 # 比如 state.pop()
back(状态，条件1，条件2，……)
return res

当然这里主要还是对于不同的题要注意不同的条件了，状态是很简单的，你就可以定义为state, 然后在for条件的时候，state加上这个值就可以了。条件的话，就是千奇百怪的了，相比较而言看你对题目的理解了，不同的题目写法是不同的，这点只能靠练了。

组合类问题

总结

  1. 遍历方向，for i in range(index,len(xx))
  2. 重复取，back(state, i), 不能重复取，back(state,i+1)
  3. 去重的，if index>i and used[i]==used[i-1] continue
1
2
3
4
5
6
7
8
9
10
11
def back(state, index):
    if xxx:
        res.append(xxx)
        return
    for i in range(index, len(xxx)):
        # 需要的话这里加上剪枝
        if index>i and used[i]==used[i-1]:
            continue
        state.append(nums[i] 或者 nums[i, index])
        back(state, i+1) #这里注意是i+1还是index+1的呢
        state.pop()

三个重点

  1. range(index,len(xxx))
  2. 剪枝
  3. i或者i+1，或者index+1

电话号码的字母组合[17]

题目见 https://leetcode.cn/problems/letter-combinations-of-a-phone-number/ , 因为在back的时候，换了一个集合了，所以back的时候，不是i或者i+1,而是index+1. 题解如下：

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
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []


        res = []
        digit_alpha_maps = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }

        def back(state, index):
            if len(state) == len(digits):
                res.append("".join(state[:]))
                return
            
            alp = digit_alpha_maps[digits[index]]
            for i in range(len(alp)):
                state.append(alp[i])
                back(state, index+1) #改动 密切注意
                state.pop()

        back([], 0)
        return res

如何看做一棵树的话，横向的是abc这种字母，纵向的就是递归，也就是index+1. 下一轮的话，是取新的字母集合了，不是刚刚的了。

组合[77]

题目见 https://leetcode.cn/problems/combinations/ ，因为不能重复取，所以back的时候，需要i+1, 题解如下：

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 back(state, index):
            if len(state) == k:
                res.append(state[:])
                return
            for i in range(index,n+1):  # 1. 不同点
                state.append(i)
                back(state, i+1)
                state.pop()
        back([], 1) # 注意，这里为1
        return res

可以看下 https://leetcode.cn/problems/combinations/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-ma-/ 他总结的还是很清晰的。

组合总和[39]

题目见 https://leetcode.cn/problems/combination-sum/ ,题目说了可以无限制取，因此back的时候，用i不用i+1.

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]]:
        res = []
        n = len(candidates)
        
        def back(state,index):
            if sum(state[:]) == target:
                res.append(state[:])
                return 
            if sum(state[:]) > target: # 注意
                return
            for i in range(index,n):
                state.append(candidates[i])
                back(state,i) # 注意
                state.pop()
        
        back([], 0)

        return res

详解看 https://programmercarl.com/0039.组合总和.html#算法公开课

组合总和 II[40]

题目在 https://leetcode.cn/problems/combination-sum-ii/ 又是求和的这道题，这道题要去重，因此在back的时候，需要i+1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 不使用used数组
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort() #注意
        res = []
        n = len(candidates)
        
        def back(state,index):
            if sum(state[:]) == target:
                res.append(state[:])
                return 
            if sum(state[:]) > target:
                return
            for i in range(index,n)     :
                if i>index and candidates[i]==candidates[i-1]: #注意
                    continue
                state.append(candidates[i])
                back(state,i+1) # 注意
                state.pop()
        
        back([], 0)

        return res

再看下这个用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 combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        res = []
        n = len(candidates)        
        def back(state,index):
            if sum(state[:]) == target:
                res.append(state[:])
                return 
            if sum(state[:]) > target:
                return
            used  = set()
            for i in range(index,n):
                if candidates[i] in used:
                    continue
                used.add(candidates[i])
                state.append(candidates[i])
                back(state,i+1)
                state.pop()
        
        back([], 0)

        return res

注意，这里很容易把used写在外面。

为何使用i>index有效果，建议看 https://leetcode.cn/problems/combination-sum-ii/solutions/14753/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-3/ 这里评论中的回复。

组合总数III[216]

题目见 https://leetcode.cn/problems/combination-sum-iii/ 题解如下：

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

        return res

套路还是一样的，依然说后面不会使用到之前的话那就可以，使用i+1来做了，其他的就很方便了。

组合总和 Ⅳ[377]

题目见 https://leetcode.cn/problems/combination-sum-iv/ 题解如下：

1
2
3
4
5
6
7
8
class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [1] + [0] * (target) # 注意
        for amount in range(target+1): # 注意
            for coins in nums:     # 注意 完全背包 排列
                if amount>=coins:       
                    dp[amount] = dp[amount] + dp[amount-coins]
        return dp[-1]

子集问题

总结

注意的是这里收集的结果是所有节点的值，不像组合是叶子节点了，其中说到底也差不多额，就是判断一下而已。

要点如下：
子集问题先排序，然后用i+1，然后不需要判断条件直接res.append(state[:]).

子集[78]

题目见 https://leetcode-cn.com/problems/subsets/ 题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def subsets(self, nums):
        res = []
        def back(state, index):
            res.append(state[:])
            for i in range(index, len(nums)):
                state.append(nums[i])
                back(state, i + 1)  # 注意点
                state.pop()
        nums.sort() # 注意点# 注意点
        back([], 0)
        print(res)
        return res

su = Solution()
su.subsets([1, 2, 3])

子集 II[90]

题目见 https://leetcode-cn.com/problems/subsets-ii/ 题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
nums.sort() # 注意点
res = []
def back(state, index):
    res.append(state[:])
    for i in range(index, len(nums)):
        if i>index and nums[i]==nums[i-1]:# 注意点
            continue
        state.append(nums[i])
        back(state, i+1) # 注意点
        state.pop()
back([], 0)
return res

分割问题

总结

就是进行for循环中，state添加数据的时候，不是back(state, s[i])了，而是back(state, s[i:i+1])了。然后是back中的i+1.

分割回文串[131]

题目见 https://leetcode.cn/problems/palindrome-partitioning/ 题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        def if_pa(x):
            return x==x[::-1]
        res = []
        def back(state, index):
            if index==len(s): # 注意点
                res.append(state[:])
                return
            for i in range(index, len(s)):
                if if_pa(s[index:i+1]): # 注意点
                    state.append(s[index:i+1]) # 注意点
                    back(state, i+1) # 注意点
                    state.pop()
        back([], 0)
        return res

复原IP地址[93]

题目在 https://leetcode.cn/problems/restore-ip-addresses/description/ ,这道题和上面峰分割类似，就是分割好了之后再判断，代码如下：

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 restoreIpAddresses(self, s: str) -> List[str]:
        def is_legal_str(x):
            int_x = int(x)
            if not str(int_x)==x:
                return False
            if int_x>255:
                return False
            return True
        
        res = []
        def back(state, index):
            if len(state)==4 and len("".join(state))==len(s):
                res.append(".".join(state))
                return
            for i in range(index, len(s)):
                if is_legal_str(s[index:i+1]):
                    state.append(s[index:i+1])
                    back(state, i+1)
                    state.pop()
        back([], 0)
        return res

排列问题

总结

遵循同样的模版，排列问题，没有start_index, back中不需要使用back(state, i+1)，需要used保存是否使用过。

打印从1到最大的n位数[LCR.135]

题目见 https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/ 题解如下

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
# 使用库的解法
class Solution:
    def printNumbers(self, n: int) -> List[int]:
        max_val = 10**n
        return list(range(1,max_val))
# 使用回溯来做
class Solution:
    def printNumbers(self, n: int) -> List[int]:
        res = []
        def back(state, digit):
            if digit == len(state):
                res.append(int("".join(state[:])))
            else:
                for i in range(10):
                    state.append(str(i))
                    back(state, digit)
                    state.pop()

        back([], n)
        return res[1:]
# 注意这里的做法
class Solution:
    def printNumbers(self, n: int):
        def dfs(num, digit):
            if len(num) == digit:
                res.append(int(''.join(num)))
                return
            for i in range(10):
                num.append(str(i))
                dfs(num, digit)
                num.pop()

        res = []
        for digit in range(1, n + 1):
            for first in range(1, 10):
                num = [str(first)]
                dfs(num, digit)

        return res

注意对于大数的处理，这里需要考虑到，不然会越界的，虽然方案2也可以通过，但是对于大数的话是不行的。

全排列[46]

遵循同样的模版，排列问题，没有start_index, back中不需要使用back(state, i+1)，需要used保存是否使用过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = []
        used = [False] * len(nums)
        def back(state):
            if len(state) == len(nums):
                res.append(state[:])
                return
            for i in range(len(nums)):
                if not used[i]: # 1. 很重要
                    state.append(nums[i])
                    used[i] = True
                    back(state) # 没要i+1
                    used[i] = False
                    state.pop()

        back([])
        return res

全排列II[47]

遵循同样的模版，排列问题，没有start_index, back中不需要使用back(state, i+1)，需要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 permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = []
        used = [False] * len(nums)

        def back(state):
            if len(state) == len(nums):
                res.append(state[:])
                return
            for i in range(len(nums)):
                if not used[i]: # 1. 很重要
                    if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]: #2.剪枝
                        continue
                    state.append(nums[i])
                    used[i] = True
                    back(state) # 没要i+1
                    used[i] = False
                    state.pop()

        back([])
        return res

矩阵类类问题

单词搜索[79]

题目见 https://leetcode.cn/problems/word-search/ ，这道题是可以使用回溯来做的，但是回溯可能会比较麻烦，而且在二维数组中的回溯相比于一维比较难写。
回溯可以使用不一样的递归来做，也是好理解的。
使用回溯法结果如下的代码

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
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m = len(board)
        n = len(board[0])

        visited = [[0]*n for _ in range(m)]
        def helper(row, col, index):
            if index == len(word):   #
                return True
            for delta_x, delta_y in [(0,1),(0,-1),(1,0),(-1,0)]:
                new_row = row + delta_x
                new_col = col + delta_y
                if 0<=new_row<m and 0<=new_col<n and not visited[new_row][new_col] and board[new_row][new_col]==word[index]:
                    visited[new_row][new_col]=1   #
                    if helper(new_row,new_col,index+1):  #
                        return True
                    visited[new_row][new_col]=0
            return False
        
        for i in range(m):
            for j in range(n):
                if board[i][j]==word[0]:
                    visited[i][j]=1  #
                    if helper(i,j,1):
                        return True
                    else:  #
                        visited[i][j] = 0
        return False

感觉上面的写法不统一，改用下面的写法：

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
class Solution:
    def __init__(self):
        self.res = False
        self.used = None
        self.len_word = 0
        self.board = None
        self.word = None

    def exist(self, board: List[List[str]], word: str) -> bool:
        self.used = [[False] * len(board[0]) for _ in range(len(board))]
        self.word = word
        self.board = board
        self.len_word = len(word)
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == word[0]:
                    self.used[i][j] = True
                    self.searchWord(i, j, 1, len(board), len(board[0]))
                    self.used[i][j] = False
        return self.res
    
    def searchWord(self, i, j, pos, m, n):
        if pos == self.len_word:
            self.res = True
            return
        for delta_x, delta_y in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
            new_x = i + delta_x
            new_y = j + delta_y
            if new_x < 0 or new_y < 0 or new_x >= m or new_y >= n or self.board[new_x][new_y] != self.word[pos] or self.used[new_x][new_y]:
                continue
            self.used[new_x][new_y] = True
            self.searchWord(new_x, new_y, pos + 1, m, n)
            self.used[new_x][new_y] = False

N皇后问题[51]

位于 https://leetcode.cn/problems/n-queens/description/ ,一般来说这种问题需要for循环进行回溯的，但是我们理清楚后可以发现，back中的index+1就可以切换到另一个循环了，和电话号码有点像。这种二维的回溯，一般一个for就可以了，然后再外围的index加上一个1.

题解如下：

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 is_check(self, state, row, col, n):
        # 检查行
        for row1 in range(n):
            if state[row1][col] == 'Q':
                return False
        # 检查列
        for col1 in range(n):
            if state[row][col1] == "Q":
                return False
        # 检查135度方向
        row1, col1 = row, col
        for i in range(n):
            row1 -= 1
            col1 -= 1
            if row1 >= 0 and col1 >= 0:
                if state[row1][col1] == "Q":
                    return False
        # 检查45度方向
        row1, col1 = row, col
        for i in range(n):
            row1 -= 1
            col1 += 1
            if row1 >= 0 and col1 <= n-1:
                if state[row1][col1] == "Q":
                    return False
        return True

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

        def back(state, row):
            if row == n:
                res.append([''.join(i) for i in state])
                return
            for col in range(n):
                if self.is_check(state, row, col, n):
                    state[row][col] = 'Q'
                    back(state, row + 1)
                    state[row][col] = "."
        back(init_state, 0)     
        return res

解数独[37]

这里直接说一下思路，back返回结果是bool类型，判断有没有解，而不是状态集合了。因此这里用两个for来循环一下的。

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
class Solution:
    def is_valid(self, row: int, col: int, val: int, board):
        # 判断同一行是否冲突
        for i in range(9):
            if board[row][i] == str(val):
                return False
        # 判断同一列是否冲突
        for j in range(9):
            if board[j][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

    def solveSudoku(self, board):
        """
        Do not return anything, modify board in-place instead.
        """

        def back(state):
            for row in range(len(board)):
                for col in range(len(board[0])):
                    if board[row][col] != '.':
                        continue
                    for k in range(1, 10):
                        if self.is_valid(row, col, k, state):
                            state[row][col] = str(k)
                            if back(state):
                                return True
                            state[row][col] = "."
                    return False
            return True
        back(board)

和单词搜索很像，虽然那道题我也用了以往回溯的思路

所有可能得路径[797]

严格意义上不算这类问题，但是仔细看，也是发现有回溯的性质在里面，题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        res = []
        
        def back(state, index):
            if index == len(graph) - 1:
                res.append(state[:])
                return
            for i in range(len(graph[index])):
                state.append(graph[index][i])
                back(state, graph[index][i])
                state.pop()
        
        state = [0]
        back(state, 0)
        return res

和电话号码有点类似，电话号码里面的是index+1,因为要取下一个数字，这里我们下一个要取得是图节点中的索引，所以直接传入节点的对应的索引就好了，这个index就是传入后，graph得到的值也是index，因此归根到底还是index，因此也符合回溯的模板。

岛屿数量[200]

代码如下：首先定义递归的出来条件，然后赋值访问过的，然后递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def dfs(grid, i, j):
            if grid[i][j]=='0':
                return
            grid[i][j] = '0'
            for delta_x, delta_y in [(0,1),(0,-1),(-1,0),(1,0)]:
                new_i = i + delta_x
                new_j = j + delta_y
                if new_i>=0 and new_i<len(grid) and new_j>=0 and new_j<len(grid[0]):                
                    dfs(grid, new_i, new_j)

        res = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j]=='1':
                    res = res + 1
                    dfs(grid,i,j)
        return res

岛屿最大面积[695]

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        def dfs(grid, i, j,current_res):
            if grid[i][j]==0:
                return
            current_res[0]= current_res[0]+1
            grid[i][j] = 0
            for delta_x, delta_y in [(0,1),(0,-1),(-1,0),(1,0)]:
                new_i = i + delta_x
                new_j = j + delta_y
                if new_i>=0 and new_i<len(grid) and new_j>=0 and new_j<len(grid[0]):                
                    dfs(grid, new_i, new_j, current_res)

        res = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j]==1:
                    current_res = [0] # 注意
                    dfs(grid,i,j,current_res)
                    res = max(res, current_res[0])
        return res

岛屿的周长[463]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        def get_nb_nums(i,j):
            cnt = 0
            for delta_x, delta_y in [(-1,0),(1,0),(0,1),(0,-1)]:
                new_i = i + delta_x
                new_j = j + delta_y
                if new_i>=0 and new_i< len(grid) and new_j>=0 and new_j<len(grid[0]) and grid[new_i][new_j]==1:
                    cnt += 1
            return cnt

        res = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    cur_bord = 4 - get_nb_nums(i,j)
                    res = res + cur_bord
        return res

最大人工岛[827]

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
DIRS = [(-1, 0), (0, 1), (1, 0), (0, -1)]
class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        n, mp, idx, size_map, res = len(grid), dict(), 0, dict(), 0

        def dfs(x, y):
            ans = 1
            mp[(x, y)] = idx
            for dx, dy in DIRS:
                if 0 <= (nx := x + dx) < n and 0 <= (ny := y + dy) < n and grid[nx][ny] and (nx, ny) not in mp:
                    ans += dfs(nx, ny)
            return ans

        for i in range(n):
            for j in range(n):
                if grid[i][j] and (i, j) not in mp:
                    size_map[idx] = dfs(i, j)
                    res = max(res, size_map[idx])
                    idx += 1

        for i in range(n):
            for j in range(n):
                if not grid[i][j]:
                    tmp, cur = set(), 1
                    for dx, dy in DIRS:
                        if 0 <= (nx := i + dx) < n and 0 <= (ny := j + dy) < n and grid[nx][ny] and mp[(nx, ny)] not in tmp:
                            tmp.add(mp[(nx, ny)])
                            cur += size_map[mp[(nx, ny)]]
                    res = max(res, cur)
        return res

查看：https://leetcode.cn/problems/making-a-large-island/solutions/1831000/-by-himymb

总结

组合总结

对于组合问题有三道题
第一道是没有重复值的，无重复值，在计算的时候back(state, i+1)
第二道题是有重复值的，可无限取，在计算的时候，back(state,i)
第三道题是有重复的，有重复值，在计算的时候，back(state,i+1)，外加剪枝，这里使用到的used[i]只是单单为了剪枝而已

排列问题

对于排列问题的两道题
第一道是没有重复值的，无重复值，在计算的时候back(state,i)，为啥要i不是i+1，因此它不是组合问题，取到一个值之后还可以往前取，如 [1,2,3] 取了2之后，还可以去2这样，因此需要使用used来判断是否之前用过，也是为了剪枝
第二道题是有重复值的，有重复值，在计算的时候back(state,i), 外加剪枝，在此使用used[i]表示一个值是否被使用过

如何剪枝

剪枝大部分的情况是为了去重，你也可以res中每进入一个新的后去重，也可以在循环里面进行判断后去重。

1
2
3
4
5
sequenceDiagram
    participant A as Alice
    participant J as John
    A->>J: Hello John, how are you?
    J->>A: Great!