抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

LeetCode-Hot100-回溯

leetcode

发布于：2024年11月15日

字数：5k 字

时长：21 分钟

前言

题单LeetCode 热题 100的回溯部分，给出解析。

46. Permutations

原题链接

题目描述

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order .

Example 1: 

1
2
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2: 

1
2
Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3: 

1
2
Input: nums = [1]
Output: [[1]]

Constraints:

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • All the integers of nums are unique .

解题方法

这个问题要求返回给定整数数组的所有可能的排列（即所有的排列组合）。

可以通过「回溯法」来解决这个问题。回溯法会递归地生成所有的排列，每次递归时我们都在当前的数字列表中选择一个数字，然后将其与其他未选择的数字进行交换。

解决思路：

  1. 回溯法：我们通过交换数组中的元素来生成每一种排列，然后递归生成后续的排列。每次选择一个元素并固定它，递归地求解剩下部分的排列，直到所有元素都被使用。

  2. 递归结束条件：当数组中的所有元素都被使用时，当前排列就是一个合法的排列，可以加入结果中。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result = []
        
        # 回溯函数
        def backtrack(path):
            # 当path的长度等于nums的长度时，说明找到一个完整的排列
            if len(path) == len(nums):
                result.append(path[:])  # 将当前路径复制一份加入结果
                return
            
            # 遍历所有数字
            for num in nums:
                if num not in path:  # 如果num不在当前路径中，才选择它
                    path.append(num)  # 做选择
                    backtrack(path)    # 递归调用
                    path.pop()         # 撤销选择，回溯

        # 调用回溯函数
        backtrack([])  
        return result

复杂度分析

时间复杂度：$O(n×n!)$，其中 $n$ 是 $nums$ 数组的长度。由于我们需要生成所有排列，每个排列的生成需要 $O(n)$ 时间，所以总的时间复杂度是 $O(n×n!)$。

空间复杂度：空间复杂度是 $O(n)$，用于存储当前递归路径 $path$。

78. Subsets

原题链接

题目描述

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order .

Example 1: 

1
2
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Example 2: 

1
2
Input: nums = [0]
Output: [[],[0]]

Constraints:

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • All the numbers of nums are unique .

解题方法

这个问题要求我们生成给定数组 nums 的所有子集，也叫幂集（power set）。根据题意，数组中的元素是唯一的，子集不能够重复。

可以使用「回溯法」（backtracking）来解决这个问题，通过递归来构建所有可能的子集。

解题思路：

  1. 递归构建子集：对于数组中的每一个元素，我们有两种选择：要么将它添加到当前子集中，要么不添加。通过这种方式，我们可以生成所有的子集。
  2. 回溯：在递归过程中，每次我们递归到一个元素时，都可以选择是否将该元素加入当前的子集，然后递归处理剩下的元素。
  3. 终止条件：当处理到数组的末尾时，将当前的子集加入到结果集中。

代码实现

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 subsets(self, nums: List[int]) -> List[List[int]]:
        """
        生成所有可能的子集（幂集）。
        :param nums: 一个包含唯一元素的整数数组
        :return: 所有可能的子集列表
        """
        # 定义结果列表
        results = []
        
        # 定义回溯函数
        def backtrack(start, path):
            # 将当前路径添加到结果中
            results.append(path[:])
            # 遍历数组中的每个元素
            for i in range(start, len(nums)):
                # 选择当前元素，并递归调用回溯函数，探索下一个元素
                path.append(nums[i])
                backtrack(i + 1, path)
                # 撤销选择，即回溯
                path.pop()
        
        # 从索引0开始回溯
        backtrack(0, [])
        
        # 返回所有子集
        return results

复杂度分析

时间复杂度：$O(2^n)$，其中 n 是数组 nums 的长度。每个元素有两种选择（在子集中或不在子集中），所以总共有 2^n 个子集。

空间复杂度：$O(n)$，递归调用栈的深度最多为 n。

17. Letter Combinations of a Phone Number

原题链接

题目描述

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order .

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1: 

1
2
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2: 

1
2
Input: digits = ""
Output: []

Example 3: 

1
2
Input: digits = "2"
Output: ["a","b","c"]

Constraints:

  • 0 <= digits.length <= 4
  • digits[i] is a digit in the range ['2', '9'].

解题方法

这个问题的目的是根据电话号码的数字映射生成所有可能的字母组合。每个数字都对应一组字母（例如，2对应”abc”，3对应”def”等）。我们需要通过遍历所有数字对应的字母组合，生成所有的可能结果。

解决思路：

  1. 映射定义： 我们首先定义一个映射关系，将每个数字（2到9）映射到对应的字母。例如，数字2映射到”abc”，数字3映射到”def”等等。

  2. 回溯法： 通过回溯的方式，逐个选择每个数字对应的字母，生成所有可能的组合。

  3. 边界情况： 当输入为空字符串时，返回一个空列表。

代码实现

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]:
        if not digits:
            return []
        
        # 映射表
        digit_to_letters = {
            '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
            '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
        }
        
        result = []
        
        # 回溯函数
        def backtrack(index, current_combination):
            # 如果当前组合的长度等于输入的数字长度，则说明生成了一个有效的组合
            if index == len(digits):
                result.append(current_combination)
                return
            
            # 当前数字对应的字母
            letters = digit_to_letters[digits[index]]
            
            # 遍历当前数字对应的每个字母
            for letter in letters:
                # 递归尝试下一个字母
                backtrack(index + 1, current_combination + letter)
        
        # 从第0个数字开始回溯
        backtrack(0, "")
        
        return result

复杂度分析

时间复杂度： 假设输入的数字长度为 $n$，每个数字对应的字母的个数（最常见的是4个字母，例如数字7和9）为 $m$。那么，生成的字母组合总数为 $m^n$，回溯的时间复杂度大约为 $O(m^n)$。

空间复杂度： 需要存储生成的所有组合，空间复杂度为 $O(m^n)$，因为最终会有 $m^n$ 个字母组合。

39. Combination Sum

原题链接

题目描述

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order .

The same number may be chosen from candidates an unlimited number of times . Two combinations are unique if the frequency of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1: 

1
2
3
4
5
6
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2: 

1
2
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3: 

1
2
Input: candidates = [2], target = 1
Output: []

Constraints:

  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • All elements of candidates are distinct .
  • 1 <= target <= 40

解题方法

这个问题可以通过回溯法来解决。题目要求找到所有和为目标值 target 的组合，其中每个候选数可以重复使用。我们可以使用递归来进行搜索，并确保每次选择候选数时，都可以再次选择当前的候选数（因此可以重复使用）。

思路：

  1. 回溯法：从候选数组 candidates 中选取数值，每次递归时，可以重复选择当前的候选数。
  2. 剪枝：为了避免重复计算，可以确保在递归时只考虑当前位置及之后的元素。这样避免了重复组合。
  3. 终止条件：当目标 target 为 0 时，意味着当前组合满足要求，可以将其加入结果列表。如果 target 小于 0，则剪枝，停止递归。

代码实现

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 combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        
        # 回溯函数
        def backtrack(start, target, current_combination):
            if target == 0:  # 目标达成
                result.append(current_combination[:])  # 保存当前的组合
                return
            if target < 0:  # 超过目标值，剪枝
                return
            
            # 遍历候选数，进行递归
            for i in range(start, len(candidates)):
                current_combination.append(candidates[i])  # 选择当前元素
                # 由于可以重复选择同一元素，递归时仍然从当前位置 i 开始
                backtrack(i, target - candidates[i], current_combination)
                current_combination.pop()  # 回溯，撤销选择
        
        # 从第一个元素开始，目标为target，当前组合为空
        backtrack(0, target, [])
        
        return result

复杂度分析

时间复杂度： 最坏情况下，递归树的深度为 $target / min(candidates)$，每次递归都会选择一个候选数进行下一个递归，因此时间复杂度近似为 $O(2^n)$，其中 $n$ 是候选数的个数。

空间复杂度： 空间复杂度主要由递归栈的深度和存储组合结果的列表决定。最坏情况下，递归深度为 $target / min(candidates)$，所以空间复杂度为 $O(target)$。

22. Generate Parentheses

原题链接

题目描述

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1: 

1
2
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2: 

1
2
Input: n = 1
Output: ["()"]

Constraints:

  • 1 <= n <= 8

解题方法

这个问题可以通过回溯（backtracking）来解决，生成所有有效的括号组合。有效的括号组合需要满足以下两个条件：

  1. 左括号的数量不能超过右括号的数量。
  2. 最终生成的括号对数为 n。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        result = []
        
        def backtrack(s, left, right):
            # 终止条件：当左括号和右括号都等于n时，说明已经生成了一个有效组合
            if left == n and right == n:
                result.append(s)
                return
            
            # 如果左括号数量小于n，可以添加一个左括号
            if left < n:
                backtrack(s + '(', left + 1, right)
            
            # 如果右括号数量小于左括号，可以添加一个右括号
            if right < left:
                backtrack(s + ')', left, right + 1)
        
        # 从空字符串开始回溯
        backtrack('', 0, 0)
        return result

复杂度分析

时间复杂度： 生成每个括号组合时，我们最多进行 $2 × n$ 次递归调用。由于每个括号组合需要考虑左右括号的排列，递归树的深度为 $2 × n$，因此时间复杂度为 $O(4^n / sqrt(n))$（卡特兰数的增长）。

空间复杂度：递归调用栈的深度是 $2 × n$，因此空间复杂度为 $O(n)$。

原题链接

题目描述

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1: 

1
2
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

Example 2: 

1
2
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

Example 3: 

1
2
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false

Constraints:

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board and word consists of only lowercase and uppercase English letters.

Follow up: Could you use search pruning to make your solution faster with a larger board?

解题方法

这个问题可以使用回溯法（Backtracking），结合深度优先搜索（DFS）技术来解决。具体步骤如下：

  1. DFS遍历：从网格中的每个单元格开始，检查能否通过递归地探索相邻的单元格（上、下、左、右）拼出给定的单词。
  2. 终止条件：如果当前已经找到单词的所有字符（即字符索引等于单词长度），返回 true。
  3. 边界条件：如果当前位置超出网格范围，或者当前单元格的字符与单词的相应字符不匹配，返回 false。
  4. 标记访问过的单元格：因为同一个单元格不能重复使用，在进行DFS搜索时，可以临时将当前单元格标记为已访问（例如，用特殊字符 # 替换）。
  5. 回溯：在探索完一个路径后，将单元格恢复成原来的字符，以便继续探索其他路径。
  6. 剪枝：如果发现某条路径不可能形成目标单词，可以提前停止，减少不必要的计算。

代码实现

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 exist(self, board: List[List[str]], word: str) -> bool:
    if not board:
        return False

    m, n = len(board), len(board[0])

    # 深度优先搜索函数
    def dfs(x, y, index):
        # 如果索引等于单词长度，表示已经找到完整单词
        if index == len(word):
            return True
        # 边界条件检查和字符匹配
        if x < 0 or x >= m or y < 0 or y >= n or board[x][y] != word[index]:
            return False
        
        # 记录当前字符的位置，避免重复使用
        temp = board[x][y]
        board[x][y] = '#'  # 标记为已访问
        
        # 向四个方向搜索
        found = (dfs(x + 1, y, index + 1) or  # 下
                 dfs(x - 1, y, index + 1) or  # 上
                 dfs(x, y + 1, index + 1) or  # 右
                 dfs(x, y - 1, index + 1))    # 左
        
        # 恢复原来的字符
        board[x][y] = temp
        
        return found

    # 遍历网格每个字符
    for i in range(m):
        for j in range(n):
            # 如果当前字符与单词的第一个字符匹配，开始搜索
            if board[i][j] == word[0] and dfs(i, j, 0):
                return True

    return False
  1. **DFS辅助函数 (dfs)**：
    • dfs(x, y, index) 函数从网格中的 (x, y) 单元格开始，寻找单词 word 中第 index 个字符。
    • 如果 index == len(word)，说明已经找到了完整的单词，返回 True。
    • 如果当前位置超出边界或者当前字符与单词不匹配，返回 False。
    • 否则，先将当前单元格标记为已访问，然后递归地向四个方向（上、下、左、右）继续搜索。
  2. **主函数 (exist)**：
    • 通过遍历网格的每个单元格，从每个单元格开始进行DFS搜索。如果某次DFS找到了单词，直接返回 True。
    • 如果所有路径都找不到，返回 False。

复杂度分析

时间复杂度：$O(m×n×4^L)$

  • $m×n$ 是网格中的单元格总数。

  • $L$ 是单词的长度。

空间复杂度：$O(L)$

  • 递归调用栈的深度最多为单词的长度 $L$。

131. Palindrome Partitioning

原题链接

题目描述

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

Example 1: 

1
2
Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

Example 2: 

1
2
Input: s = "a"
Output: [["a"]]

Constraints:

  • 1 <= s.length <= 16
  • s contains only lowercase English letters.

解题方法

这个问题要求我们将字符串 s 切分成若干个子串，使得每个子串都是回文字符串，然后返回所有可能的回文切分方式。

解题思路：

  1. 回文判断：首先需要判断一个子串是否是回文字符串。可以通过双指针的方式检查字符串的两端是否相等来判断。

  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 partition(self, s: str) -> List[List[str]]:
        result = []
    
        def is_palindrome(sub_str: str):
            return sub_str == sub_str[::-1]
        
        def backtrack(start: int, path: list):
            if start == len(s):  # 如果到达字符串的末尾，说明找到了一种分割方案
                result.append(path[:])  # 复制当前路径，添加到结果中
                return
            
            for end in range(start + 1, len(s) + 1):
                substr = s[start:end]  # 获取当前的子串
                if is_palindrome(substr):
                    path.append(substr)  # 如果是回文串，将其加入当前路径
                    backtrack(end, path)  # 递归处理剩余的字符串
                    path.pop()  # 回溯，撤销上一步的选择
        
        backtrack(0, [])
        return result

复杂度分析

时间复杂度： 由于我们需要遍历字符串的所有可能切分方式，因此最坏情况下时间复杂度是指数级别的：$O(2^n)$，其中 $n$ 是字符串的长度。

空间复杂度：$O(n)$，其中 $n$ 是字符串的长度。

51. N-Queens

原题链接

题目描述

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return _all distinct solutions to the n-queens puzzle . You may return the answer in any order .

Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

Example 1: 

1
2
3
Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

Example 2: 

1
2
Input: n = 1
Output: [["Q"]]

Constraints:

  • 1 <= n <= 9

解题方法

这个问题是典型的回溯算法问题。通过递归尝试每一行上放置皇后，并通过剪枝避免攻击其他已放置的皇后，从而求出所有的解法。

思路：

  1. 回溯法：我们从第一行开始，依次尝试将皇后放在每一列上，如果当前放置的皇后不与之前放置的皇后相互攻击（即不在同一列、同一斜线），则递归到下一行。否则，尝试下一列的位置。
  2. 剪枝条件：
    • 列冲突：通过一个集合记录已经被占用的列。
    • 主对角线冲突：通过一个集合记录已经被占用的主对角线（i - j）。
    • 副对角线冲突：通过一个集合记录已经被占用的副对角线（i + j）。

代码实现

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]]:
        def backtrack(row, cols, diag1, diag2, current_solution):
            # 如果所有行都放置了皇后，说明找到一个解
            if row == n:
                result.append([''.join(row) for row in current_solution])
                return
            
            for col in range(n):
                # 检查当前列和两个对角线是否有冲突
                if col in cols or (row - col) in diag1 or (row + col) in diag2:
                    continue
                
                # 做选择，放置皇后
                cols.add(col)
                diag1.add(row - col)
                diag2.add(row + col)
                current_solution[row][col] = 'Q'
                
                # 继续放置下一个皇后
                backtrack(row + 1, cols, diag1, diag2, current_solution)
                
                # 撤销选择
                cols.remove(col)
                diag1.remove(row - col)
                diag2.remove(row + col)
                current_solution[row][col] = '.'
        
        result = []
        current_solution = [['.' for _ in range(n)] for _ in range(n)]
        cols = set()
        diag1 = set()
        diag2 = set()
        
        backtrack(0, cols, diag1, diag2, current_solution)
        return result

代码解释：

  1. backtrack 函数是递归函数，row 表示当前处理的行，columns，diag1，diag2 分别是用于记录被占用的列、主对角线、副对角线的集合。
  2. current_board 代表当前棋盘的状态，使用二维数组 board 来表示，Q 表示皇后，. 表示空位。
  3. 每当一行的所有列都尝试完毕且没有冲突时，就将当前的棋盘布局作为解加入 result。
  4. 通过回溯的方式，尝试每一个列的可能，确保每次放置皇后时都不会发生冲突，若有冲突则跳过当前列。

复杂度分析

时间复杂度： $O(n!)$，这是因为每一行最多可以放置一个皇后，并且在最坏情况下需要探索每一种可能的布局。

空间复杂度： $O(n^2)$。

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://blog.skyheart.moe/posts/c664530a/

更新于：2024年11月15日

回溯

评论