image.png

⼀、全排列问题

https://leetcode-cn.com/problems/permutations/
image.pngimage.pngimage.png

  1. def traverse(root:TreeNode):
  2.      for child in root.childern:
  3.             # 前序遍历需要的操作 
  4.             traverse(child)
  5.             # 后序遍历需要的操作

image.png
image.png

  1. for 选择 in 选择列表:
  2.     # 做选择
  3.     将该选择从选择列表移除 
  4.     路径.add(选择) 
  5.     backtrack(路径, 选择列表) 
  6.     # 撤销选择 
  7.     路径.remove(选择) 
  8.     将该选择再加⼊选择列表

image.png\
https://leetcode-cn.com/problems/permutations/

  1. class Solution:
  2.     def permute(self, nums: List[int]) -> List[List[int]]:
  3.         res = []
  4.         def backtrack(path=[], selects=nums):
  5.             if not selects:   # 结束条件，选择列表为空
  6.                 res.append(path[:])
  7.                 return
  8.             for i in range(len(selects)):
  9.                 path.append(selects[i])   # 做出选择
  10.                 backtrack(path, selects[:i] + selects[i+1:])#后面这个索引排除了不合法的选择
  11.                 path.pop()   # 取消选择
  12.         backtrack()
  13.         return res

image.png

⼆、N 皇后问题

https://leetcode-cn.com/problems/n-queens/
image.png

  1. class Solution:
  2.     def solveNQueens(self, n: int) -> List[List[str]]:
  3.         board = [['.' for _ in range(n)] for _ in range(n)]  #初始化棋盘：字符串在python中为不可变量，故先用list[char]表示，再用''.join()拼接
  4.         res=[]    #存放最终结果
  6.         def DFS(res,row):#按行进行递归，当每一行都有一个皇后时即为满足条件返回一个结果。
  7.             #递归基：若所有行都已放好Q，把结果写入,返回
  8.             if row == n:
  9.                 temp=[]
  10.                 for line in board:
  11.                     t = ''.join(line)
  12.                     temp.append(t[:])
  13.                 res.append(temp[:])
  14.                 return
  15.             #对该行的每一位置进行判断，找到适合放Q的位置，再递归深入到下一行，
  16.             #到最后一行记录结果，并从下一行回溯到本行时恢复标记回溯到上行，
  17.             for col in range(len(board[row])):
  18.                 if not isValid(row,col):continue#这个位置无效，判断下一个位置
  19.                 #若这个位置有效
  20.                 board[row][col] = 'Q'#找到位置添加标记
  21.                 DFS(res,row+1)#深入到下一行搜索可能位置
  22.                 board[row][col] = '.'#从下一行回溯到本行时恢复标记
  23.         DFS(res,0)  #DFS搜索
  24.         return res
  1.         def isValid(row,col):#判断（row,col）是否可行
  2.             #逐行递归，判断(row,col)的每行/列/主对角/副对角是否只在(row,col)处有'Q'
  3.             #判断row行：判断[row,0:col-1]是否有'Q'
  4.             for c in range(col):#c:0->col-1
  5.                 if board[row][c] == 'Q':return False
  6.             #判断col列：判断[0:row-1,col]是否有'Q'
  7.             for r in range(row):#r:0->row-1
  8.                 if board[r][col] == 'Q':return False
  9.             #判断(左上角)主对角线：判断[0:row-1,0:col-1]是否有'Q'
  10.             mrow, mcol = row, col
  11.             while mrow > 0 and mcol > 0:#mrow:0->row-1,mcol:0->row-1
  12.                 mrow-=1
  13.                 mcol-=1
  14.                 if board[mrow][mcol] == 'Q':return False
  15.             #判断(右上角)副对角线：判断[0:row-1,col+1:n]
  16.             vrow, vcol = row, col
  17.             while vrow > 0 and vcol < n-1:#vrow:0->row-1,vcol:col+1->n
  18.                 vrow-=1
  19.                 vcol+=1
  20.                 if board[vrow][vcol] == 'Q':return False
  21.             return True

image.png

image.png

  1.        def DFS(res,row):
  2.             if row == n:
  3.                 temp=[]
  4.                 for line in board:
  5.                     t = ''.join(line)
  6.                     temp.append(t[:])
  7.                 res.append(temp[:])
  8.                 return True   # 这里
  10.             for col in range(len(board[row])):
  11.                 ...
  12.                 board[row][col] = 'Q'
  13.                 if(DFS(res,row+1)) : return True   # 这里 
  14.                 board[row][col] = '.'
  15.             return False   # 这里
  16.         DFS(res,0)  
  17.         return res

三、最后总结

image.pngimage.png