三个月算法进阶--day15
目录
深度优先遍历（回溯）
回到上一个节点时之前做了什么，之后就要做相应的逆操作，即“状态重置”
递归终止条件
状态：每一个结点表示了求解问题的不同阶段
python函数传列表再append是原地修改，append的项是列表要复制
记录
leetcode第46题全排列
时间复杂度：O(n X n!)，递归树的深度为n
状态变量：
- 递归到第几层depth
- 已经选了哪些数path，这个列表只在末尾操作，所以是个栈
- 布尔数组used，不用遍历即可知道数是否被使用，以O(1)的时间复杂度完成判断
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
length = len(nums)
depth = 0
ans = []
path = []
used = [False] * length
self.dfs(nums, length, depth, path, used, ans)
return ans
def dfs(self, nums, length, depth, path, used, ans):
if depth == length:
ans.append(path[:]) # 一次拷贝
for i, t in enumerate(nums):
if used[i] == True:
continue
else:
path.append(t)
used[i] = True
self.dfs(nums, length, depth+1, path, used, ans)
used[i] = False # 回溯
path.pop()
class Solution:
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
def backtrack(first = 0):
# 所有数都填完了
if first == n:
res.append(nums[:])
for i in range(first, n):
# 动态维护数组
nums[first], nums[i] = nums[i], nums[first]
# 继续递归填下一个数
backtrack(first + 1)
# 撤销操作
nums[first], nums[i] = nums[i], nums[first]
n = len(nums)
res = []
backtrack()
return res
感受
回溯算法体现了算法的精妙，不掌握难以解决特定问题。