算法长征（10）回溯

发表于 更新于 分类于 ， 阅读次数： 本文字数： 8.5k 阅读时长 ≈ 15 分钟

回溯 - 子集、组合、排列、岛屿

result = [] def backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择

39.组合总和

40. 组合总和 II

46. 全排列

47. 全排列 II

78. 子集

90. 子集 II

给定一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

1
2
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        ans = []
        def backtrace(idx, tmp):
            ans.append(tmp[:])
            for j in range(idx, n):
                tmp.append(nums[j])
                backtrace(j + 1, tmp)
                tmp.pop()
        backtrace(0, [])
        return ans
    def subsets(self, nums: List[int]) -> List[List[int]]:
        # import itertools.combinations
        ans = []
        for i in range(len(nums) + 1):
            for tmp in itertools.combinations(nums, i):
                ans.append(tmp)
        return ans

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

例如，在下面的 3×4 的矩阵中包含单词 "ABCCED"（单词中的字母已标出）。

img 
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 exist(self, board: List[List[str]], word: str) -> bool:
      m = len(board)
      n = len(board[0])
      def dfs(x, y, index):
           if index == len(word):
           		return True
           for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
               nx, ny = x + dx, y + dy
               if 0 <= nx < m and 0 <= ny < n and board[nx][ny] == word[index]:
                   board[nx][ny] = '/'
               		 if dfs(nx, ny, index + 1):
                       return True
                   board[nx][ny] = word[index]
            return False
      for i in range(m):
          for j in range(n):
              if board[i][j] == word[0]:
                  board[i][j] = '/'
              		if dfs(i, j, 1):
                  		return True
               		board[i][j] = word[0]
      return False

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

  • bfs、bfs、岛屿面积
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
class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        # bfs
        def sum_(x, y):
            return x%10 + x//10 +  y%10 + y//10
        que = collections.deque()
        que.append((0, 0))
        s = set()
        s.add((0, 0))
        while que:
            x, y = que.popleft()
            for i, j in [(x + 1, y), (x, y + 1)]:
                if 0 <= i < m and 0 <= j < n and (i, j) not in s and sum_(i,j) <= k:
                    que.append((i, j))
                    s.add((i, j))
        return len(s)
    def movingCount(self, m: int, n: int, k: int) -> int:
        # dfs【向下向右】
        def dfs(i: int, j: int) -> int:
            if i >= m or j >= n or sum_(i, j) > k or f[i][j] == 1:
                return 0
            f[i][j] = 1
            return 1 + dfs(i + 1, j) + dfs(i, j + 1)

        def sum_(x, y):
            return x%10 + x//10 +  y%10 + y//10
        
        f = [[0 for i in range(n)] for j in range(m)]
        return dfs(0, 0)

    def movingCount(self, m: int, n: int, k: int) -> int:
        # 回溯: 岛屿面积  
        def sumGrid(x, y):
            return x%10 + x//10 +  y%10 + y//10
        visited = set()
        def backtrace(x, y):
            visited.add((x, y))
            for i, j in [(x-1, y), (x, y-1), (x, y+1), (x+1, y)]:
                if 0 <= i < m and 0<= j < n and (i, j) not in visited and sumGrid(i, j) <= k:
                    backtrace(i, j)
        backtrace(0, 0)
        return len(visited)

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出==所有==从根节点到叶子节点 路径总和等于给定目标和的路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def pathSum(self, root: TreeNode, target: int) -> List[List[int]]:
        def backtrace(root, tmp, target):
            if not root:
                return
            if not root.left and not root.right and target == root.val:
                ans.append(tmp[:] + [root.val])
                return
            tmp.append(root.val)
            backtrace(root.left, tmp, target - root.val)
            backtrace(root.right, tmp, target - root.val)
            tmp.pop()
        ans = []
        backtrace(root, [], target)
        return ans

  • https://leetcode.cn/problems/zi-fu-chuan-de-pai-lie-lcof/solution/dai-ma-sui-xiang-lu-jian-zhi-offer-38-zi-gwt6/

输入一个字符串，打印出该字符串中字符的所有排列。

  • 还要强调的是==去重一定要对元素经行排序==，这样我们才方便通过相邻的节点来判断是否重复使用了。
  • 组合问题和排列问题是在树形结构的叶子节点上收集结果，而子集问题就是取树上所有节点的结果。
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 permutation(self, s: str) -> List[str]:
        # itertools.permutations(s)
        return list(set("".join(t) for t in itertools.permutations(s)))
    
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        if not nums: 
            return []
        res = []
        used = set() # [0] * len(nums)
        def backtracking(path):
            if len(path) == len(nums):
                res.append(path[:])
                return
            for i in range(len(nums)):
                if i not in used:
                    if i>0 and nums[i] == nums[i-1] and i-1 not in used:
                      	# 重复剪枝
                        continue
                    used.add(i)
                    path.append(nums[i])
                    backtracking(path)
                    path.pop()
                    used.remove(i)
        # 记得给nums排序
        nums.sort()
        backtracking([])
        return res

给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是不同的。

输入: candidates = [2,3,6,7], target = 7 输出: [[7],[2,2,3]]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        # 回溯，无重复元素，根据剩余值凑成目标
        ans = []
        path = []
        candidates.sort() # 预先排序，
        # 收集逻辑为target == 0

        def backtracking(index,path,target):
            if index >= len(candidates) or target < 0:
                return 
            if target == 0: # 收集条件
                ans.append(path[:])
                return    
            for i in range(index,len(candidates)):  # 注意可以重复收集          
                path.append(candidates[i])  # 做选择
                backtracking(i,path,target-candidates[i])
                path.pop() # 取消选择
         
        backtracking(0,[],target)
        return ans

给定一个可能有重复数字的整数数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次，解集不能包含重复的组合。

1
2
3
4
5
6
7
8
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        ans, n = [], len(candidates)
        candidates.sort()
        def backtrace(idx, tmp, target):
            if idx > n or target < 0:
                return
            if target == 0:
                ans.append(tmp[:])
                return
            for i in range(idx, n):
                if i > idx and candidates[i] == candidates[i - 1]:
                    # 去重：让递归的同一级不出现相同元素、递归的不同级可以出现相同元素
                    continue
                tmp.append(candidates[i])
                backtrace(i + 1, tmp, target - candidates[i])
                tmp.pop()
        backtrace(0, [], target)
        return ans

给定一个不含重复数字的整数数组 nums ，返回其 所有可能的全排列 。可以 按任意顺序 返回答案。

输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

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]]:
        # 库函数[数组交换]、回溯模版
        # return list(itertools.permutations(nums))
        ans, n = [], len(nums)
        visited = set()
        def backtrace(idx, tmp):
            if len(tmp) == n:
                ans.append(tmp[:])
                return 
            for i in range(n):
                if i not in visited:
                    visited.add(i)
                    tmp.append(nums[i])
                    backtrace(i + 1, tmp)
                    tmp.pop()
                    visited.remove(i)
        backtrace(0 ,[])
        return ans

给定一个可包含重复数字的整数集合 nums ，按任意顺序 返回它所有不重复的全排列。

输入：nums = [1,1,2] 输出： [[1,1,2], [1,2,1], [2,1,1]]

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]]:
        # visited 记录访问节点的集合
        n = len(nums)
        ans = []
        vis = set()
        def backtrace(tmp):
            if len(tmp) == n:
                ans.append(tmp[:])
                return 
            for i in range(n):
                if i in vis:
                    continue
                if i > 0 and nums[i] == nums[i - 1] and i - 1 not in vis:
                    # not in 保留顺序剪枝 
                    continue
                vis.add(i)
                backtrace(tmp + [nums[i]])
                vis.remove(i)
        nums.sort()
        backtrace([])
        return ans

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]

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 generateParenthesis(self, n: int) -> List[str]:
        # 回溯
        # 第一步：得到全部 2^(2n) 种组合，然后再根据我们刚才总结出的合法括号组合的性质筛选出合法的组合
        # 第二步：剪枝  1、可用左括号大于右括号 2、括号可用小于0
        ans = []
        def backtrace(left, right, tmp):
            if left > right:
                return
            if left < 0  or right < 0:
                return
            if left == 0 and right == 0:
                ans.append("".join(tmp[:]))
                return
            tmp.append('(')
            backtrace(left - 1, right, tmp)
            tmp.pop()

            tmp.append(')')
            backtrace(left, right - 1, tmp)
            tmp.pop()
        backtrace(n, n, [])
        return ans

给定一个字符串 s ，请将 s 分割成一些子串，使每个子串都是 回文串 ，返回 s 所有可能的分割方案。回文串 是正着读和反着读都一样的字符串。

输入：s = "google" 输出：[["g","o","o","g","l","e"],["g","oo","g","l","e"],["goog","l","e"]]

  • 动态规划预处理 + 回溯全排列
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 partition(self, s: str) -> List[List[str]]:
        # 动态规划预处理 + 回溯全排列条件
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = True
        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                if s[i] == s[j]:
                    if j - i <= 1 or dp[i + 1][j - 1]:
                        dp[i][j] = True
        ans = []
        def backtrace(idx, tmp):
            if idx == n:
                ans.append(tmp[:])
                return
            for i in range(idx, n):
                if dp[idx][i]:
                    tmp.append(s[idx: i + 1])
                    backtrace(i + 1, tmp)
                    tmp.pop()
        backtrace(0, [])
        return ans

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

  • 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

输入：s = "25525511135" 输出：["255.255.11.135","255.255.111.35"]

「力扣」第 93 题：复原 IP 地址-1.png

  • 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯;
  • 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0;
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 restoreIpAddresses(self, s: str) -> List[str]:
        SEG_COUNT = 4
        ans = list()
        segments = [0] * SEG_COUNT
        def dfs(segId: int, segStart: int):
            # 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案
            if segId == SEG_COUNT:
                if segStart == len(s):
                    ipAddr = ".".join(str(seg) for seg in segments)
                    ans.append(ipAddr)
                return
            # 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯
            if segStart == len(s):
                return
            # 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0
            if s[segStart] == "0":
                segments[segId] = 0
                dfs(segId + 1, segStart + 1)
            # 一般情况，枚举每一种可能性并递归
            addr = 0
            for segEnd in range(segStart, len(s)):
                addr = addr * 10 + (ord(s[segEnd]) - ord("0"))
                if 0 < addr <= 0xFF:
                    segments[segId] = addr
                    dfs(segId + 1, segEnd + 1)
                else:
                    break
        dfs(0, 0)
        return ans