class Solution:
def generateParenthesis(self, n: int) -> List[str]:
self.ans = []
self._gen(0,0,n,"")
return self.ans
def _gen(self,left,right,n,result):
if left == n and right == n :
self.ans.append(result)
return
if left < n:
self._gen(left+1,right,n,result+"(")
if left > right and right < n :
self._gen(left,right+1,n,result+")")
剪枝：
遍历二叉树，有些节点不用看的，可以找局部最优分支
N皇后问题：
思路：
最后输出的两种棋盘可以先简化成 [[1,3,0,2],[2,0,3,1]] 再去定义一个函数画出来
用DFS的方法去遍历棋盘上的每一个位置，DFS用row来递归，当row = n 的时候递归停止
每个递归内部 用 col循环每一列的每个位置来做判断。
判断标准：
3个set来储存不能放置的col, pie, na。每放置一枚棋子，不能放置的col,pie,na就多一组。
为什么用set?
假设 初始棋子在（1，0）（row, col） 虽然不可能。如果这样 na里面 col- row则为负数。用set去存好一点。且set可以减少重复的pie, na存储
如果判断通过，则到下一层。
下一层遍历完之后，更新同层的另外的位置的时候要删去假设这个位置被占，下一层不能放置的col,pie,na
自己有问题的代码：
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
self.result = []
self.col,self.pie,self.na = set(),set(),set();
self.solve(0,n,[])
return self.gen_result(n)
def solve(self,row,n,cur):
if row >= n-1:
self.result.append(cur)
cur = []
for col in n:
if col in self.col or col-row in na or col + row in pie:
continue
self.col.add(col)
self.pie.add(col+row)
self.na.add(col-row)
self.solve(row+1,n,cur+[col])
self.col.remove(col)
self.pie.remove(col+row)
self.na.remove(col-row)
def gen_result(self,n):
ans = []
for res in self.result:
innerans = []
for i in res:
innerans.append(i*"."+"Q"+(n-i+1)*".")
ans.append(innerans)
return ans
修改调整过后：
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
self.result = []
self.col,self.pie,self.na = set(),set(),set();
self.solve(0,n,[])
return self.gen_result(n)
def solve(self,row,n,cur):
if row >= n:
self.result.append(cur)
cur = []
for col in range(n):
if col in self.col or col-row in self.na or col + row in self.pie:
continue
self.col.add(col)
self.pie.add(col+row)
self.na.add(col-row)
self.solve(row+1,n,cur+[col])
self.col.remove(col)
self.pie.remove(col+row)
self.na.remove(col-row)
def gen_result(self,n):
ans = []
for res in self.result:
innerans = []
for i in res:
innerans.append(i*"."+"Q"+(n-i-1)*".")
ans.append(innerans)
return ans
出错的问题：
1. 从0 到 n-1 的循环，for col in range(n) 不是 for col in n
2. 调用对象内部的公有/私有变量的时候记得加self. 调用对象内部的函数也需要加
52.
class Solution:
def totalNQueens(self, n: int) -> int:
self.ans_num = 0
self.col,self.pie,self.na = set(),set(),set()
self.dfs(n,0)
return self.ans_num
def dfs(self,n,row):
if row == n:
self.ans_num += 1
for col in range(n):
if col in self.col or col + row in self.pie or col-row in self.na:
continue
self.col.add(col)
self.pie.add(col+row)
self.na.add(col-row)
self.dfs(n,row+1)
self.col.remove(col)
self.pie.remove(col+row)
self.na.remove(col-row)
36 37.数独：
错误写法1：
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
return self.solve(board)
def solve(self, board):
for i in range(9):
for j in range(9):
if board[i][j] == '.':
for c in range(1,10):
if self.is_valid(board,i,j,str(c)):
board[i][j] = str(c)
if(solve(board)):
return True
return False
return True
def is_valid(self,board,i,j,c):
for char!='.' in board[i][:]:
if c == char:
return False
for char!='.' in board[:][j]:
if c == char:
return False
x = i//3
y = j//3
for char!='.' in board[3x:3x+3][3j:3j+3]:
if c == char:
return False
return True
存在的问题：
1.is_valid那里 python for循环的结构没有搞清楚
2.在递归的时候，如果solve(board) 算出来是false,会退到上一层，把上一层的同位置置为'.'
3.遍历完1-9都没有找到解，就return False
正确写法1：
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
self.solve(board)
def solve(self, board):
for i in range(9):
for j in range(9):
if board[i][j] == '.':
for c in range(1,10):
if self.is_valid(board,i,j,str(c)):
board[i][j] = str(c)
if(self.solve(board)):
return True
else:
board[i][j] = '.'
return False
return True
def is_valid(self,board,row,col,c):
for i in range(9):
if (board[i][col] != '.' and board[i][col] == c):
return False
if (board[row][i] != '.' and board[row][i] == c):
return False
x = row //3
y = col //3
if (board[3*x + i//3][3*y + i%3] != '.' and board[3*x + i//3][3*y + i%3] == c):
return False
return True
正确写法2：优化了一些
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
self.solve(board,0,0)
def solve(self, board,i,j):
if j == 9 :
return self.solve(board,i+1,0)
if i == 9:
return True
if board[i][j] != '.':
return self.solve(board, i, j+1)
for n in range(1, 10):
c = str(n)
if self.is_valid(board, i, j, c):
board[i][j] = c
if self.solve(board,i,j+1):
return True
board[i][j] = '.'
return False
def is_valid(self,board,row,col,c):
for i in range(9):
if (board[i][col] != '.' and board[i][col] == c):
return False
if (board[row][i] != '.' and board[row][i] == c):
return False
x = row //3
y = col //3
if (board[3*x + i//3][3*y + i%3] != '.' and board[3*x + i//3][3*y + i%3] == c):
return False
return True
减少了循环的次数
注意：基本情况里，如果有的话一定记得return
总结：
DFS回溯法框架：