回溯法模板：
result = []
def backtrack(路径, 选择列表):#这里的路径也就是初试根节点，选择列表是初始化列表if 满足结束条件:result.add(路径)returnfor 选择 in 选择列表:#这里选择是可能的所有节点做选择 #把节点放入选择列表中backtrack(路径, 选择列表) #像下一级节点（决策树）搜索撤销选择 #通常这里的操作跟做选择相反
全排列：
List<List<Integer>> res = new LinkedList<>();/* 主函数，输入一组不重复的数字，返回它们的全排列 */
List<List<Integer>> permute(int[] nums) {// 记录「路径」LinkedList<Integer> track = new LinkedList<>();backtrack(nums, track);return res;
}// 路径：记录在 track 中
// 选择列表：nums 中不存在于 track 的那些元素
// 结束条件：nums 中的元素全都在 track 中出现
void backtrack(int[] nums, LinkedList<Integer> track) {// 触发结束条件if (track.size() == nums.length) {res.add(new LinkedList(track));return;}for (int i = 0; i < nums.length; i++) {// 排除不合法的选择if (track.contains(nums[i]))continue;// 做选择track.add(nums[i]);// 进入下一层决策树backtrack(nums, track);// 取消选择track.removeLast();}
}N皇后：
vector<vector<string>> res;/* 输入棋盘边长 n，返回所有合法的放置 */
vector<vector<string>> solveNQueens(int n) {// '.' 表示空，'Q' 表示皇后，初始化空棋盘。vector<string> board(n, string(n, '.'));backtrack(board, 0);return res;
}// 路径：board 中小于 row 的那些行都已经成功放置了皇后
// 选择列表：第 row 行的所有列都是放置皇后的选择
// 结束条件：row 超过 board 的最后一行
void backtrack(vector<string>& board, int row) {// 触发结束条件if (row == board.size()) {res.push_back(board);return;}int n = board[row].size();for (int col = 0; col < n; col++) {// 排除不合法选择if (!isValid(board, row, col)) continue;// 做选择board[row][col] = 'Q';// 进入下一行决策backtrack(board, row + 1);// 撤销选择board[row][col] = '.';}
}
/* 是否可以在 board[row][col] 放置皇后？ */
bool isValid(vector<string>& board, int row, int col) {int n = board.size();// 检查列是否有皇后互相冲突for (int i = 0; i < n; i++) {if (board[i][col] == 'Q')return false;}// 检查右上方是否有皇后互相冲突for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {if (board[i][j] == 'Q')return false;}// 检查左上方是否有皇后互相冲突for (int i = row - 1, j = col - 1;i >= 0 && j >= 0; i--, j--) {if (board[i][j] == 'Q')return false;}return true;
}leetcode77-组合：
class Solution:def combine(self, n: int, k: int) -> List[List[int]]:def backtrack(first = 1, curr = []):# if the combination is doneif len(curr) == k: output.append(curr[:])#这里不能用curr，而是用curr[:]，因为回溯时，curr改变则 #output在内存中也会改变。而curr[:]则是先将curr完全复制#再赋值给output。后面curr的改变不再影响outputfor i in range(first, n + 1):# add i into the current combinationcurr.append(i)# use next integers to complete the combinationbacktrack(i + 1, curr)# backtrackcurr.pop()output = []backtrack()return output