《Leetcode》-面试题-hot100-回溯

题目列表

题目

（1）全排列

题目

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 1 <= nums.length <= 6

• -10 <= nums[i] <= 10

• nums 中的所有整数 互不相同

思路

class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
result = []
self.backtracking(nums, [], [False] * len(nums), result)
return result

def backtracking(self, nums, path, used, result):
if len(path) == len(nums):
result.append(path[:])
return
for i in range(len(nums)):
if used[i]:
continue
used[i] = True
path.append(nums[i])
self.backtracking(nums, path, used, result)
path.pop()
used[i] = False

（2）子集

题目

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

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

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

示例 2：

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

提示：

• 1 <= nums.length <= 10

• -10 <= nums[i] <= 10

• nums 中的所有元素 互不相同

思路

class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
result = []
path = []
self.backtracking(nums, 0, path, result)
return result

def backtracking(self, nums, startIndex, path, result):
result.append(path[:]) # 收集子集，要放在终止添加的上面，否则会漏掉自己
# if startIndex >= len(nums): # 终止条件可以不加
# return
for i in range(startIndex, len(nums)):
path.append(nums[i])
self.backtracking(nums, i + 1, path, result)
path.pop()

（3）电话号码的数字组合

题目

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 0 <= digits.length <= 4

• digits[i] 是范围 ['2', '9'] 的一个数字。

思路

class Solution:
def __init__(self):
self.letterMap = [
"", # 0
"", # 1
"abc", # 2
"def", # 3
"ghi", # 4
"jkl", # 5
"mno", # 6
"pqrs", # 7
"tuv", # 8
"wxyz" # 9
]
self.result = []
self.s = ""

def backtracking(self, digits, index):
if index == len(digits):
self.result.append(self.s)
return
digit = int(digits[index]) # 将索引处的数字转换为整数
letters = self.letterMap[digit] # 获取对应的字符集
for i in range(len(letters)):
self.s += letters[i] # 处理字符
self.backtracking(digits, index + 1) # 递归调用，注意索引加1，处理下一个数字
self.s = self.s[:-1] # 回溯，删除最后添加的字符

def letterCombinations(self, digits: str) -> List[str]:
if len(digits) == 0:
return self.result
self.backtracking(digits, 0)
return self.result

（4）组合总和

题目

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 1 <= candidates.length <= 30

• 2 <= candidates[i] <= 40

• candidates 的所有元素 互不相同

• 1 <= target <= 40

思路

class Solution:
def backtracking(self, candidates, target, total, startIndex, path, result):
if total == target:
result.append(path[:])
return

for i in range(startIndex, len(candidates)):
if total + candidates[i] > target:
break
total += candidates[i]
path.append(candidates[i])
self.backtracking(candidates, target, total, i, path, result)
total -= candidates[i]
path.pop()

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
result = []
candidates.sort() # 需要排序
self.backtracking(candidates, target, 0, 0, [], result)
return result

（5）括号生成

题目

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

示例 1：

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

示例 2：

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

提示：

• 1 <= n <= 8

思路

class Solution:
def generateParenthesis(self, n: int) -> List[str]:
if n == 0:
return ['']
ans = []
for c in range(n):
for left in self.generateParenthesis(c):
for right in self.generateParenthesis(n-1-c):
ans.append('({}){}'.format(left, right))
return ans

#题解：https://leetcode.cn/problems/generate-parentheses/solutions/192912/gua-hao-sheng-cheng-by-leetcode-solution/

（6）单词搜索

题目

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

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

示例 1：

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

示例 2：

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

示例 3：

输入：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 仅由大小写英文字母组成

思路

class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
def dfs(i, j, k, row, col, list_set, board, path):
if k == len(word):
return True
for x, y in list_set:
word_x = i + x
word_y = j + y
if 0<= word_x<row and 0<=word_y<col and board[word_x][word_y] == word[k] and (word_x, word_y) not in path:
path.add((word_x, word_y))
if dfs(word_x, word_y, k+1, row, col, list_set, board, path):
return True
path.remove((word_x, word_y))

row = len(board)
col = len(board[0])
list_set = [(-1, 0), (1, 0), (0, -1), (0, 1)]
k = 1
for i in range(row):
for j in range(col):
if board[i][j] == word[0] and dfs(i, j, k, row, col, list_set, board, {(i, j)}):
return True
return False

（7）分割回文串

题目

给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

示例 1：

输入：s = "aab" 输出：[["a","a","b"],["aa","b"]]

示例 2：

输入：s = "a" 输出：[["a"]]

提示：

• 1 <= s.length <= 16

• s 仅由小写英文字母组成

思路

class Solution:
def partition(self, s: str) -> List[List[str]]:
'''
递归用于纵向遍历
for循环用于横向遍历
当切割线迭代至字符串末尾，说明找到一种方法
类似组合问题，为了不重复切割同一位置，需要start_index来做标记下一轮递归的起始位置(切割线)
'''
result = []
self.backtracking(s, 0, [], result)
return result

def backtracking(self, s, start_index, path, result ):
# Base Case
if start_index == len(s):
result.append(path[:])
return

# 单层递归逻辑
for i in range(start_index, len(s)):
# 此次比其他组合题目多了一步判断：
# 判断被截取的这一段子串([start_index, i])是否为回文串
if self.is_palindrome(s, start_index, i):
path.append(s[start_index:i+1])
self.backtracking(s, i+1, path, result) # 递归纵向遍历：从下一处进行切割，判断其余是否仍为回文串
path.pop() # 回溯

def is_palindrome(self, s: str, start: int, end: int) -> bool:
i: int = start
j: int = end
while i < j:
if s[i] != s[j]:
return False
i += 1
j -= 1
return True

（8）N皇后

题目

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

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

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

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：

输入：n = 4 输出：[[".Q..","…Q","Q…","..Q."],["..Q.","Q…","…Q",".Q.."]] 解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1 输出：[["Q"]]

提示：

• 1 <= n <= 9

思路

class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
def generateBoard():
board = list()
for i in range(n):
row[queens[i]] = "Q"
board.append("".join(row))
row[queens[i]] = "."
return board

def backtrack(row: int):
if row == n:
board = generateBoard()
solutions.append(board)
else:
for i in range(n):
if i in columns or row – i in diagonal1 or row + i in diagonal2:
continue
queens[row] = i
columns.add(i)
diagonal1.add(row – i)
diagonal2.add(row + i)
backtrack(row + 1)
columns.remove(i)
diagonal1.remove(row – i)
diagonal2.remove(row + i)

solutions = list()
queens = [-1] * n
columns = set()
diagonal1 = set()
diagonal2 = set()
row = ["."] * n
backtrack(0)
return solutions

#链接：https://leetcode.cn/problems/n-queens/solutions/398929/nhuang-hou-by-leetcode-solution/
# 时间复杂度：O(N!)，其中 N 是皇后数量。
# 空间复杂度：O(N)，其中 N 是皇后数量。空间复杂度主要取决于递归调用层数、记录每行放置的皇后的列下标的数组以及三个集合，递归调用层数不会超过 N，数组的长度为 N，每个集合的元素个数都不会超过 N。

结尾

亲爱的读者朋友：感谢您在繁忙中驻足阅读本期内容！您的到来是对我们最大的支持❤️

正如古语所言："当局者迷，旁观者清"。您独到的见解与客观评价，恰似一盏明灯💡，能帮助我们照亮内容盲区，让未来的创作更加贴近您的需求。

若此文给您带来启发或收获，不妨通过以下方式为彼此搭建一座桥梁： ✨ 点击右上角【点赞】图标，让好内容被更多人看见 ✨ 滑动屏幕【收藏】本篇，便于随时查阅回味 ✨ 在评论区留下您的真知灼见，让我们共同碰撞思维的火花

我始终秉持匠心精神，以键盘为犁铧深耕知识沃土💻，用每一次敲击传递专业价值，不断优化内容呈现形式，力求为您打造沉浸式的阅读盛宴📚。

有任何疑问或建议？评论区就是我们的连心桥！您的每一条留言我都将认真研读，并在24小时内回复解答📝。

愿我们携手同行，在知识的雨林中茁壮成长🌳，共享思想绽放的甘甜果实。下期相遇时，期待看到您智慧的评论与闪亮的点赞身影✨！

自我介绍：一线互联网大厂资深算法研发（工作6年+），4年以上招聘面试官经验（一二面面试官，面试候选人400+），深谙岗位专业知识、技能雷达图，已累计辅导15+求职者顺利入职大中型互联网公司。熟练掌握大模型、NLP、搜索、推荐、数据挖掘算法和优化，提供面试辅导、专业知识入门到进阶辅导等定制化需求等服务，助力您顺利完成学习和求职之旅（有需要者可私信联系） 

友友们，自己的知乎账号为“快乐星球”，定期更新技术文章，敬请关注！