回溯52-59

52. 全排列给定一个不含重复数字的数组nums返回其所有可能的全排列。你可以按任意顺序返回答案。class Solution(object): def fun(self,nums,path): if len(path)len(nums): self.res.append(path[:]) for i in range(len(nums)): if self.visit[i]0: self.visit[i]1 path.append(nums[i]) self.fun(nums,path) path.pop() self.visit[i]0 def permute(self, nums): self.res[] self.visit[0]*len(nums) self.fun(nums,[]) return self.res53. 子集给你一个整数数组nums数组中的元素互不相同。返回该数组所有可能的子集幂集。解集不能包含重复的子集。你可以按任意顺序返回解集。class Solution(object): def fun(self,nums,path,x): self.res.append(path[:]) for i in range(x,len(nums)): path.append(nums[i]) self.fun(nums,path,i1) path.pop() def subsets(self, nums): self.res[] self.fun(nums,[],0) return self.res54. 电话号码的字母组合给定一个仅包含数字2-9的字符串返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。class Solution(object): def letterCombinations(self, digits): mp{ 2:[a,b,c], 3:[d,e,f], 4:[g,h,i], 5:[j,k,l], 6:[m,n,o], 7:[p,q,r,s], 8:[t,u,v], 9:[w,x,y,z] } res[] for _ in digits: if not res: resmp[_] else: ans[] for c in mp[_]: for s in res: ans.append(.join(sc)) resans return res55. 组合总和给你一个无重复元素的整数数组candidates和一个目标整数target找出candidates中可以使数字和为目标数target的 所有不同组合并以列表形式返回。你可以按任意顺序返回这些组合。candidates中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同则两种组合是不同的。对于给定的输入保证和为target的不同组合数少于150个。class Solution(object): def fun(self,candidates,target,x,path): if target0 and xlen(candidates): self.res.append(path[:]) for i in range(x,len(candidates)): if target-candidates[i]0: path.append(candidates[i]) self.fun(candidates,target-candidates[i],i,path) path.pop() def combinationSum(self, candidates, target): candidatessorted(candidates) self.res[] self.fun(candidates,target,0,[]) return self.res56. 括号生成数字n代表生成括号的对数请你设计一个函数用于能够生成所有可能的并且有效的括号组合。class Solution(object): def sun(self,left,right,path): if left0 and right0: self.res.add(.join(path[:])) if left0: path.append(() self.sun(left-1,right1,path) path.pop() if right0: path.append()) self.sun(left,right-1,path) path.pop() def generateParenthesis(self, n): self.resset() self.sun(n,0,[]) return list(self.res)57. 单词搜索给定一个m x n二维字符网格board和一个字符串单词word。如果word存在于网格中返回true否则返回false。单词必须按照字母顺序通过相邻的单元格内的字母构成其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。class Solution(object): def DFS(self,board,word,i,j,m,n,k): if i0 and im and j0 and jn and self.visit[i][j]0: if board[i][j]word[k]: self.visit[i][j]1 if klen(word)-1: return True for x,y in self.dir: x,yxi,yj if self.DFS(board,word,x,y,m,n,k1): return True self.visit[i][j]0 def exist(self, board, word): self.dir[[0,1],[0,-1],[1,0],[-1,0]] m,nlen(board),len(board[0]) self.visit[[0]*n for i in range(m)] for i in range(m): for j in range(n): if board[i][j]word[0]: if self.DFS(board,word,i,j,m,n,0): return True return False58. 分割回文串给你一个字符串s请你将s分割成一些 子串使每个子串都是回文串。返回s所有可能的分割方案。class Solution(object): def is_palindrome(self, sub): if subsub[::-1]: return True return False def backtrack(self, s, start, path): if startlen(s): self.res.append(path[:]) for end in range(start,len(s)): if self.is_palindrome(s[start:end1]): path.append(s[start:end1]) self.backtrack(s,end1,path) path.pop() def partition(self, s): self.res[] self.backtrack(s,0,[]) return self.res59. N 皇后按照国际象棋的规则皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n 皇后问题研究的是如何将n个皇后放置在n×n的棋盘上并且使皇后彼此之间不能相互攻击。给你一个整数n返回所有不同的n皇后问题的解决方案。每一种解法包含一个不同的n 皇后问题的棋子放置方案该方案中Q和.分别代表了皇后和空位。class Solution(object): def judge(self,i,j,n): x, y i - 1, j - 1 while x 0 and y 0: if self.visit[x][y] Q: return False x - 1 y - 1 x, y i - 1, j 1 while x 0 and y n: if self.visit[x][y] Q: return False x - 1 y 1 return True def fun(self,n,row): if rown: self.res.append([.join(_[:]) for _ in self.visit]) return for col in range(n): if self.col[col] 0: if self.judge(row,col,n): self.visit[row][col]Q self.col[col]1 self.fun(n,row1) self.visit[row][col]. self.col[col]0 def solveNQueens(self, n): self.dir[[0,1],[1,0],[0,-1],[-1,0],[1,1],[1,-1],[-1,1],[-1,-1]] self.visit[[.]*n for _ in range(n)] self.col[0]*n self.res[] self.fun(n,0) return self.res