！！！牢记模板！！！
result = [] def backtrack(选择列表, 路径): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: # 做选择 路径.add(选择) 将该选择从选择列表移除 backtrack(选择列表, 路径) # 核心 递归调用之前【做选择】，调用之后【撤销选择】 # 撤销选择 路径.remove(选择) 将该选择再加入选择列表
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
class Solution: def permute(self, nums): res = [] # 选择列表就是nums包含的元素 # 使用used标记已经选择的数字 间接表示选择列表的变化 def backtrack(path, used): # 结束条件 if len(path) == len(nums): res.append(path[:]) # ！！！此处有坑需要注意 return for i in range(len(nums)): if used[i]: # nums[i]已经选过 跳过 continue # 做选择 path.append(nums[i]) used[i] = True # 更新选择列表 # 递归 backtrack(path, used) # 撤销选择 path.pop() used[i] = False # 回退选择列表的变化 # 初始时路径为空，所有元素都没有选择过所以used中都是False used = [False]*len(nums) path = [] backtrack(path, used) return res
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
class Solution(object): def subsets(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ res = [] def backtrack(path, start): res.append(path[:]) if len(path) == len(nums): return for i in range(start, len(nums)): path.append(nums[i]) # 递归 backtrack(path, i+1) # 从下一元素开始 避免重复 path.pop() path, start = [], 0 backtrack(path, start) return res
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
digits.length = 0: return []
digits.length = 1: return ['x','y','z']
digits.length = k: k个组合中各挑一个字母组合
class Solution(object): def letterCombinations(self, digits): """ :type digits: str :rtype: List[str] """ tmp = {'2':'abc', '3':'def', '4':'ghi', '5':'jkl', '6':'mno', '7': 'pqrs', '8':'tuv', '9':'wxyz'} strr = [] for i in digits: strr.append(tmp[i]) length = len(strr) if length == 0: return [] elif length == 1: return [i for i in strr[0]] res = [] def backtrack(path, start): if len(path) == len(strr): res.append(''.join(path)) return for i in range(start, len(strr)): for j in range(len(strr[i])): path.append(strr[i][j]) backtrack(path, i+1) path.pop() path, start = [], 0 backtrack(path, start) return res
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。candidates 中的 同一个 数字可以 无重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 对于给定的输入，保证和为 target 的不同组合数少于 150 个。
candidates = [1,2,3] tartget = 5
会出现[1,1,3]-[1,3,1]的重复情况，因此需要将可选范围在当前值（可重复选取）或之后；
class Solution(object): def combinationSum(self, candidates, target): """ :type candidates: List[int] :type target: int :rtype: List[List[int]] """ res = [] def backtrack(path, start): summ = sum(path) if summ >= target: # 终止条件不再长度 if summ== target:res.append(path[:]) return for i in range(start, len(candidates)): path.append(candidates[i]) backtrack(path, i) # 当前元素和之后的可重复选取 path.pop() path, start = [], 0 backtrack(path, start) return res
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
‘(’代表+1，‘)’代表-1，终止条件：sum(path)出现负数时结束，len(path)==2*n时结束；
class Solution(object): def generateParenthesis(self, n): """ :type n: int :rtype: List[str] """ res = [] inputt = ['(', ')'] def backtrack(path, summ): if summ < 0: return if len(path) == 2*n: if summ == 0: res.append(''.join(path)) return for i in range(len(inputt)): path.append(inputt[i]) summ += (1 if inputt[i]=='(' else -1) backtrack(path, summ) strr = path.pop() summ -= (1 if strr=='(' else -1) path, summ = [], 0 backtrack(path, summ) return resDFS：记录左括号和右括号的数量；
class Solution: def generateParenthesis(self, n): res = [] def dfs(paths, left, right): if left > n or right > left: return if len(paths) == n * 2: # 因为括号都是成对出现的 res.append(paths) return dfs(paths + '(', left + 1, right) # 生成一个就加一个 dfs(paths + ')', left, right + 1) dfs('', 0, 0) return res
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
先遍历一次，找到所有字符串单词首字母在网格中的位置；
从首字母的网格位置入手，先加入当前字母，然后在不越界的情况下加入上/下/左/右的字母，判断加入的第n个字母是否和word中第n个字母相同；
class Solution(object): def exist(self, board, word): """ :type board: List[List[str]] :type word: str :rtype: bool """ res = [] m, n, k = len(board), len(board[0]), len(word) if m*n < k: return False # 元素不够 def backtrack(path, cnt, pos): if path[-1] != word[cnt-1]: return else: if cnt == k: res.append(path[:]) return for i,j in [[-1,0],[1,0],[0,-1],[0,1]]: x, y = pos[0]+i, pos[1]+j if -1<x<m and -1<y<n and board[x][y]: path.append(board[x][y]) cnt, board[x][y] = cnt+1, '' backtrack(path, cnt, [x, y]) # 从下一元素开始 避免重复 board[x][y] = path.pop() cnt -= 1 first_alpha = [] for i in range(m): for j in range(n): if board[i][j] == word[0]: first_alpha.append([i,j]) if len(first_alpha)==0: return False # 没有首字母 for i,j in first_alpha: path, cnt = [board[i][j]], 1 board[i][j] = '' backtrack(path, cnt, [i, j]) board[i][j] = word[0] return bool(res)可以优化的地方：1.不需要记录path；2.找到一个word就可以结束；（需要backtrack回传）3.改变传入的cnt即可；
class Solution(object): def exist(self, board, word): """ :type board: List[List[str]] :type word: str :rtype: bool """ m, n, k = len(board), len(board[0]), len(word) if m*n < k: return False # 元素不够 def backtrack(cnt, pos): if board[pos[0]][pos[1]] != word[cnt]: return False if cnt == k-1: return True board[pos[0]][pos[1]] = '' for i,j in [[-1,0],[1,0],[0,-1],[0,1]]: x, y = pos[0]+i, pos[1]+j if -1<x<m and -1<y<n and board[x][y]: if backtrack(cnt+1, [x, y]): return True board[pos[0]][pos[1]] = word[cnt] first_alpha = [] for i in range(m): for j in range(n): if board[i][j] == word[0]: first_alpha.append([i,j]) if len(first_alpha)==0: return False # 没有首字母 for i,j in first_alpha: if backtrack(0, [i, j]): return True return False
131 分割回文串
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串。返回 s 所有可能的分割方案。
子串的选择范围需要从下一字符开始，因此需要起始位置；
加入path的子串必须是回文子串，需要先判断再加入，因此把枚举范围从单个字符变成字符串长度，然后验证当前长度的子串是否是回文；
终止条件：长度到达终点；
class Solution(object): def partition(self, s): """ :type s: str :rtype: List[List[str]] """ res = [] length = len(s) def backtrack(path, start): if start == length: res.append(path[:]) return for i in range(start, length): # 枚举的是回文子串的长度 tmp = s[start:i+1] if tmp==tmp[::-1]: path.append(tmp) backtrack(path, i+1) path.pop() path, start = [], 0 backtrack(path, start) return res
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
搬运【山鬼】的解析：
1. 从上往下放棋子，用变量的表示就是，row从0到n-1
2.backtrack()函数的参数为row，表示当前开始放第row行的皇后，小于row的行（row行往上的）都已经放置皇后了
3. 需要构建一个isValid()函数，参数为board,row,col，返回是否可以在row,col上合法放置皇后；这个函数需要沿着row,col判断这个位置的上方、右上方、左上方是否有皇后。
因篇幅问题不能全部显示，请点此查看更多更全内容