leetcode刷题记录——回溯

17 电话号码的字母组合 Medium

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

img

示例 1：

1
2
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

1
2
输入：digits = ""
输出：[]

示例 3：

1
2
输入：digits = "2"
输出：["a","b","c"]

提示：

  • 0 <= digits.length <= 4
  • digits[i] 是范围 ['2', '9'] 的一个数字。

思路

首先建立好映射，初始化我们需要存储的数组一个存储结果一个辅助我们的过程

后续使用回溯算法进行递归就OK了

代码

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:
    dict = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
    def __init__(self):
        self.total = []
        self.res = []
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return self.total
        # 从第一个数字开始  
        self.backtrack(digits, 0)
        return self.total
    def backtrack(self, digits: str, start: int) -> None:
        if len(self.res) == len(digits):
            # 到达回溯树底部
            self.total.append(''.join(self.res))
            return
        digit = ord(digits[start]) - ord('0')
        for i in self.dict[digit]:
            # 做选择
            self.res.append(i)
            # 递归下一层
            self.backtrack(digits, start + 1)
            # 撤销选择
            self.res.pop()

时间复杂度

时间复杂度$O(4 ^n)$，空间复杂度$O(n * 4 ^ n)$，执行时间24ms，消耗内存16.4MB

77 组合 Medium

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

1
2
3
4
5
6
7
8
9
10
输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2：

1
2
输入：n = 1, k = 1
输出：[[1]]

提示：

  • 1 <= n <= 20
  • 1 <= k <= n

思路

依旧是模板题，不过要注意的是，起始位置为1，存储为list

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
        def backtrack(first = 1, curr = []):
            if len(curr) == k:
                res.append(curr[:])
                return
            for i in range(first, n + 1):
                curr.append(i)
                backtrack(i + 1, curr)
                curr.pop()
        backtrack(1, [])
        return res

时间复杂度

时间复杂度O(k * C(n, k))，空间复杂度O(k * C(n, k))，执行时间190ms，消耗内存57.4MB

这里的C(n, k)涉及到组合公式（说实话我都不太会算了，高中学完，大学学完概率论就不咋用了，隐隐约约记得高中那会还总结了一个快速算法，排列问题也有一个）

公式为 $C(n, k) = \frac{n!}{k!(n - k)!}$

46 全排列 Medium

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • nums 中的所有整数 互不相同

思路

还是模板，只不过这里在回溯部分需要改为换位置

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        def backtrack(first = 0):
            if first == len(nums):
                res.append(nums[:])
                return 
            for i in range(first, len(nums)):
                nums[first], nums[i] = nums[i], nums[first]
                backtrack(first + 1)
                nums[first], nums[i] = nums[i], nums[first]
                
        backtrack()
        return res

时间复杂度

时间复杂度O(n * n!)，空间复杂度O(n * n!)，执行时间27ms，消耗内存16.7MB

组合总和 Medium

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

1
2
3
4
5
6
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

1
2
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

1
2
输入: candidates = [2], target = 1
输出: []

提示：

  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • candidates 的所有元素 互不相同
  • 1 <= target <= 40

思路

还是模板题，这里需要注意的是，我们的 backtrack 函数需要涉及到四个东西，数组 candidates 结果 target 起始点 first 加和 sum

别的其实和第一题如出一辙

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def __init__(self):
        self.res = []
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        if not candidates:
            return self.res
        self.backtrack(candidates, target, 0, 0)
        return self.res
    track = []
    def backtrack(self, candidates: List[int], target: int, first: int, sum: int) -> None:
        if sum == target:
            self.res.append(self.track.copy())
            return
        if sum > target:
            return
        for i in range(first, len(candidates)):
            self.track.append(candidates[i])
            sum += candidates[i]
            self.backtrack(candidates, target, i, sum)
            sum -= candidates[i]
            self.track.pop()

时间复杂度

时间复杂度O(n^(target/min(candidates)))，空间复杂度O(target/min(candidates))，执行时间62ms，消耗内存16.6MB

52 N 皇后 II Hard

n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。

示例 1：

img

1
2
3
输入：n = 4
输出：2
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

1
2
输入：n = 1
输出：1

提示：

  • 1 <= n <= 9

思路

这道题唯一需要注意的就是在该位置能不能放皇后，由于我们遍历过程中左下右下并未涉及到，所以我们只需要看右上左上有没有皇后就可以

代码

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 __init__(self):
        self.res = 0
    def totalNQueens(self, n: int) -> int:
        board = ['.' * n for _ in range(n)]
        self.backtrack(board, 0)
        return self.res
    
    def backtrack(self, board, row):
        if row == len(board):
            self.res += 1
            return
        n = len(board[row])
        for col in range(n):
            if not self.isValid(board, row, col):
                continue
            board[row] = board[row][:col] + 'Q' + board[row][col + 1:]
            self.backtrack(board, row + 1)
            board[row] = board[row][:col] + '.' + board[row][col + 1:]
            
    def isValid(self, board, row, col):
        n = len(board)
        for i in range(0, row + 1):
            if board[i][col] == 'Q':
                return False
        for i, j, in zip(range(row - 1, -1, -1), range(col + 1, n)):
            if board[i][j] == 'Q':
                return False
        for i, j in zip(range(row - 1, -1, -1), range(col - 1, -1, -1)):
            if board[i][j] == 'Q':
                return False
        return True

时间复杂度

时间复杂度O(N!)，空间复杂度O(N)，执行时间101ms，消耗内存16.4MB

22 括号生成 Medium

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

示例 1：

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

示例 2：

1
2
输入：n = 1
输出：["()"]

提示：

  • 1 <= n <= 8

思路

没啥好说的，就是套模板，直接看代码

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        if n == 0:
            return []
        res = []
        self.dfs(n, n, '', res)
        return res
    def dfs(self, left, right, path, res):
        if left == 0 and right == 0:
            res.append(path)
            return
        if left > 0:
            self.dfs(left - 1, right, path + '(', res)
        if right > left:
            self.dfs(left, right - 1, path + ')', res)

时间复杂度

时间复杂度$(O(4^n / \sqrt{n})$，空间复杂度O(n)，执行时间44ms，消耗内存16.6MB

79 单词搜索 Medium

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

img

1
2
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

示例 2：

img

1
2
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true

示例 3：

img

1
2
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false

提示：

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board 和 word 仅由大小写英文字母组成

思路

注意需要寻找四个方向看有没有，然后注意需要借助一个符号标记已经遍历过

代码

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 __init__(self):
        self.found = False
    def exist(self, board: List[List[str]], word: str) -> bool:
        row, col = len(board), len(board[0])
        for i in range(row):
            for j in range(col):
                self.dfs(board, i, j, word, 0)
                if self.found:
                    return True
        return False
    def dfs(self, board, i, j, word, k):
        if k == len(word):
            self.found = True
            return 
        if self.found:
            return 
        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or word[k] != board[i][j]:
            return
        tmp = board[i][j]
        board[i][j] = '#'
        self.dfs(board, i + 1, j, word, k + 1)
        self.dfs(board, i - 1, j, word, k + 1)
        self.dfs(board, i, j + 1, word, k + 1)
        self.dfs(board, i, j - 1, word, k + 1)
        board[i][j] = tmp

时间复杂度

时间复杂度$ O(m * n * 4^L)$，空间复杂度O(L)，执行时间3876ms，消耗内存16.4MB

模板

1
2
3
4
5
6
7
8
9
10
result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择
刷题记录
#Leetcode #刷题 #回溯
leetcode刷题记录——回溯
https://www.lx02918.ltd/2024/08/29/leetcode-回溯/
作者
Seth
发布于
2024年8月29日
许可协议