说明

回溯问题，实际上决策树遍历问题。只需思考3个问题：

  • 路径：已做的选择；
  • 选择列表：当前可以做的选择；
  • 结束条件：无法再做选择的条件。

框架

  1. result = []
  2. def backtrack(路径, 选择列表):
  3.     if 满足结束条件:
  4.         result.add(路径)
  5.         return
  7.     for 选择 in 选择列表:
  8.         做选择
  9.         backtrack(路径, 选择列表)
  10.         撤销选择

全排列问题

获取全排列的所有路径。这里假设n个数都不相同，则共有n！条路径。

必读系列 4回溯算法解题套路框架 - 图1

  1. List<List<Integer>> res = new LinkedList<>();
  3. List<List<Integer>> permute(int[] nums) {
  4.     LinkedList<Integer> track = new LinkedList<>();
  5.     backtrace(nums, track);
  6.     return res;
  7. }
  9. void backtrack(int[] nums, LinkedList<Integer> track) {
  10.     // 结束 触发
  11.     if(tack.size() == nums.length) {
  12.         res.add(new LinkedList(track));
  13.         return;
  14.     }
  16.     for(int i = 0; i < nums.length; i++) {
  17.         // 排除不合法的选择
  18.         if(track.contains(nums[i]))
  19.             continue;
  20.         // 做选择
  21.         track.add(nums[i]);
  22.         // 进入下一层决策树
  23.         backtrack(nums, track);
  24.         // 撤销选择
  25.         track.reomveLast();
  26.     }
  27. }

N 皇后问题

给你一个 N×N 的棋盘，让你放置 N 个皇后，使得它们不能互相攻击。皇后可以攻击同一行、同一列、左上左下右上右下四个方向的任意单位。

必读系列 4回溯算法解题套路框架 - 图2

  1. List<List<String>> res = new LinkedList<>();
  3. // 输入 棋盘 边长n ， 返回所有的 合法 放置
  4. List<List<String>>  solveNQueues(int n) {
  5.     // '.' 表示空， 'Q'表示皇后 初始化空棋盘
  6.     List<String> borad;
  8.     backtrack(board, 0);
  9.     return res
  10.  }
  12. // 路径: board中 小于row的那些行已经成功放置了皇后
  13. // 选择列表: 第row行所以的列都是放置皇后的选择
  14. // 结束条件：row 超过 board 的最后一行
  16. void backtrack(List<String> board, int row) {
  17.     // 已经超过最后一行,保存当前棋盘的状况
  18.     if(row == board.size()) {
  19.         res.add(board);
  20.         return;
  21.     }
  22.     // 一行就是一个字符串 获取长度
  23.     int len = board.get(row).length();
  24.     for(int col = 0; col < len; col++) {