leetcode-top100回溯算法

本文主要是介绍leetcode-top100回溯算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

组合总和

题目链接

39. 组合总和 - 力扣（LeetCode）

解题代码

class Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:def dfs(candidates,begin,size,path,res,target):if target < 0:returnif target == 0:res.append(path)returnfor index in range(begin,size):dfs(candidates,index,size,path + [candidates[index]],res,target - candidates[index])size = len(candidates)if size == 0:return []path = []res = []dfs(candidates,0,size,path,res,target)return res

括号生成

题目链接

22. 括号生成 - 力扣（LeetCode）

解题代码

class Solution:def generateParenthesis(self, n: int) -> List[str]:if n == 0 :return []def generate(A):if len(A) == 2*n:if valid(A):ans.append("".join(A))else:A.append("(")generate(A)A.pop()A.append(")")generate(A)A.pop()def valid(A):bal = 0for c in A:if c == '(': bal += 1else: bal -= 1if bal < 0: return Falsereturn bal == 0ans = []generate([])return ans

单词搜索

题目链接

79. 单词搜索 - 力扣（LeetCode）

解题代码

class Solution:def exist(self, board: List[List[str]], word: str) -> bool:directions = [(1,0),(-1,0),(0,1),(0,-1)]def check(i: int, j:int, k:int) ->bool:if board[i][j] != word[k]:return Falseif k == len(word) - 1:return Truevisited.add((i,j))result = Falsefor di,dj in directions:newi, newj = i + di,j + djif 0 <= newi < len(board) and 0 <= newj < len(board[0]):if (newi,newj) not in visited:if check(newi,newj,k + 1):result = Truebreakvisited.remove((i,j))return resulth,w = len(board),len(board[0])visited = set()for i in range(h):for j in range(w):if check(i,j,0):return Truereturn False

分割回文串

题目链接

131. 分割回文串 - 力扣（LeetCode）

解题代码

class Solution:def partition(self, s: str) -> List[List[str]]:n = len(s)f = [[True] * n for _ in range(n)]for i in range(n - 1, -1, -1):for j in range(i + 1, n):f[i][j] = (s[i] == s[j]) and f[i+1][j-1]ret = list()ans = list()def dfs(i:int):if i == n:ret.append(ans[:])returnfor j in range(i,n):if f[i][j]:ans.append(s[i:j + 1])dfs(j + 1)ans.pop()dfs(0)return ret

N皇后

题目链接

51. N 皇后 - 力扣（LeetCode）

解题代码

class Solution:def solveNQueens(self, n: int) -> List[List[str]]:def generateBoard():board = list()for i in range(n):row[queens[i]] = "Q"board.append("".join(row))row[queens[i]] = "."return boarddef backtrack(row: int):if row == n:board = generateBoard()solutions.append(board)else:for i in range(n):if i in columns or row - i in diagonal1 or row + i in diagonal2:continuequeens[row] = icolumns.add(i)diagonal1.add(row - i)diagonal2.add(row + i)backtrack(row + 1)columns.remove(i)diagonal1.remove(row - i)diagonal2.remove(row + i)solutions = list()queens = [-1] * ncolumns = set()diagonal1 = set()diagonal2 = set()row = ["."] * nbacktrack(0)return solutions

这篇关于leetcode-top100回溯算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---