直接上框架
result = [] def backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: # 做选择 将该选择从选择列表移除 路径.add(选择) backtrack(路径, 选择列表) # 撤销选择 路径.remove(选择) 将该选择再加入选择列表直接看全排列的代码
import java.util.ArrayList; import java.util.List; public class Solution { /* 主函数，输入一组不重复的数字，返回它们的全排列 */ public List<List<Integer>> permute(int[] nums) { int len = nums.length; // 使用一个动态数组保存所有可能的全排列 List<List<Integer>> res = new ArrayList<>(); if (len == 0) { return res; } //保存已经否被被访问的状态 boolean[] used = new boolean[len]; // 记录「路径」 List<Integer> path = new ArrayList<>(); dfs(nums, len, 0, path, used, res); return res; } // 路径：记录在 path 中 // 选择列表：nums 中不存在于 track 的那些元素 // 结束条件：nums 中的元素全都在 track 中出现 private void dfs(int[] nums, int len, int depth, List<Integer> path, boolean[] used, List<List<Integer>> res) { if (depth == len) { res.add(new ArrayList<>(path)); return; } // 在非叶子结点处，产生不同的分支，这一操作的语义是：在还未选择的数中依次选择一个元素作为下一个位置的元素，这显然得通过一个循环实现。 for (int i = 0; i < len; i++) { // 排除不合法的选择 if (!used[i]) { // 做选择 path.add(nums[i]); used[i] = true; // 进入下一层决策树 dfs(nums, len, depth + 1, path, used, res); // 注意：下面这两行代码发生 「回溯」，回溯发生在从 深层结点 回到 浅层结点 的过程，代码在形式上和递归之前是对称的 // 取消选择 used[i] = false; path.remove(path.size() - 1); } } } public static void main(String[] args) { int[] nums = {1, 2, 3}; Solution solution = new Solution(); List<List<Integer>> lists = solution.permute(nums); System.out.println(lists); } }c++
bool vis[N]; // 访问标记数组 int a[N]; // 排列数组，按顺序储存当前搜索结果 void dfs(int step) { if (step == n + 1) { // 边界 for (int i = 1; i <= n; i++) { cout << setw(5) << a[i]; } cout << endl; return; } for (int i = 1; i <= n; i++) { if (vis[i] == 0) { vis[i] = 1; a[step] = i; dfs(step + 1); vis[i] = 0; } } return; }N×N 的棋盘，让你放置 N 个皇后，使得它们不能互相攻击。
PS：皇后可以攻击同一行、同一列、左上左下右上右下四个方向的任意单位。
这个问题本质上跟全排列问题差不多，决策树的每一层表示棋盘上的每一行；每个节点可以做出的选择是，在该行的任意一列放置一个皇后。
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; }写 backtrack 函数时，需要维护走过的「路径」和当前可以做的「选择列表」，当触发「结束条件」时，将「路径」记入结果集。
