回溯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.res

53. 子集

给你一个整数数组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,i+1) path.pop() def subsets(self, nums): self.res=[] self.fun(nums,[],0) return self.res

54. 电话号码的字母组合

给定一个仅包含数字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: res=mp[_] else: ans=[] for c in mp[_]: for s in res: ans.append("".join(s+c)) res=ans return res

55. 组合总和

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

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

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

class Solution(object): def fun(self,candidates,target,x,path): if target==0 and x<len(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): candidates=sorted(candidates) self.res=[] self.fun(candidates,target,0,[]) return self.res

56. 括号生成

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

class Solution(object): def sun(self,left,right,path): if left==0 and right==0: self.res.add("".join(path[:])) if left>0: path.append("(") self.sun(left-1,right+1,path) path.pop() if right>0: path.append(")") self.sun(left,right-1,path) path.pop() def generateParenthesis(self, n): self.res=set() 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 i>=0 and i<m and j>=0 and j<n and self.visit[i][j]==0: if board[i][j]==word[k]: self.visit[i][j]=1 if k==len(word)-1: return True for x,y in self.dir: x,y=x+i,y+j if self.DFS(board,word,x,y,m,n,k+1): return True self.visit[i][j]=0 def exist(self, board, word): self.dir=[[0,1],[0,-1],[1,0],[-1,0]] m,n=len(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 False

58. 分割回文串

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

class Solution(object): def is_palindrome(self, sub): if sub==sub[::-1]: return True return False def backtrack(self, s, start, path): if start==len(s): self.res.append(path[:]) for end in range(start,len(s)): if self.is_palindrome(s[start:end+1]): path.append(s[start:end+1]) self.backtrack(s,end+1,path) path.pop() def partition(self, s): self.res=[] self.backtrack(s,0,[]) return self.res

59. 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 row==n: 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,row+1) 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