框架

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

例题

全排列

回溯法 - 图1

class Solution {
    private List<List<Integer>> result;
    public List<List<Integer>> permute(int[] nums) {
        LinkedList<Integer> track = new LinkedList<>();
        result = new LinkedList<>();
        backtrack(nums, track);
        return result;
    }
    private void backtrack(int[] nums, LinkedList<Integer> track) {
        // end condition
        if (track.size() == nums.length) {
            // Create a new List object, otherwise subsequent track changes will affect the result
            result.add(new LinkedList(track));
            return;
        }
        for (int i = 0; i < nums.length; ++i) {
            // Rule out illegal choices
            if (track.contains(nums[i])) continue;
            // Make a choice
            track.add(nums[i]);
            System.out.println("递归前：" + track + " i = " + i);
            // Enter the next level of decision tree
            backtrack(nums, track);
            // Revoke the choice
            track.removeLast();
            System.out.println("递归后：" + track + " i = " + i);
        }
    }
}

递归前：[1] i = 0
递归前：[1, 2] i = 1
递归前：[1, 2, 3] i = 2
递归后：[1, 2] i = 2 // 为什么会继续撤销？因为i已经遍历到最后，函数正常结束了，回到上一层。
递归后：[1] i = 1
递归前：[1, 3] i = 2
递归前：[1, 3, 2] i = 1
递归后：[1, 3] i = 1
递归后：[1] i = 2
递归后：[] i = 0
递归前：[2] i = 1
递归前：[2, 1] i = 0
递归前：[2, 1, 3] i = 2
递归后：[2, 1] i = 2
递归后：[2] i = 0
递归前：[2, 3] i = 2
递归前：[2, 3, 1] i = 0
递归后：[2, 3] i = 0
递归后：[2] i = 2
递归后：[] i = 1
递归前：[3] i = 2
递归前：[3, 1] i = 0
递归前：[3, 1, 2] i = 1
递归后：[3, 1] i = 1
递归后：[3] i = 0
递归前：[3, 2] i = 1
递归前：[3, 2, 1] i = 0
递归后：[3, 2] i = 0
递归后：[3] i = 1
递归后：[] i = 2

track.contains()需要O(N)时间，也可以用一个boolean数组存储是否已经使用过，来代替contains。

result.add()的时候不能直接添加track，而是要拷贝一个List对象，否则因为引用传递的机制，track被添加进result以后还是会不断变化，影响最终结果。

二叉树中和为某一值的路径

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
  private List<List<Integer>> result;
  private LinkedList<Integer> trace;
  public List<List<Integer>> pathSum(TreeNode root, int sum) {
      result = new LinkedList<>();   
      trace = new LinkedList<>();
      if (root == null) return result;
      dfs(root, sum);
      return result;
  }
  private void dfs(TreeNode node, int target) {
      if (node == null) return;
      target -= node.val;
      trace.add(node.val);
      // if each nodel.val != 0
      if (target == 0 && node.right == null && node.left == null)
          result.add(new LinkedList(trace));
      dfs(node.left, target);
      dfs(node.right, target);
      trace.removeLast();
      target += node.val;
  }
}

这题稍微有一点不一样的是，需要在添加了一个路径后立即判断是否满足target然后加入result，因为需要确定这个node是不是叶节点，因为如果放到下一层判断node == null也不表示上一层node就是叶节点（有左右两个方向）。

N皇后

回溯法 - 图2 ```java class Solution {

private int n; // 某一列是否放了Q private boolean[] col; // 某一主对角线是否放了Q private boolean[] main; // 某一副对角线是否放了Q private boolean[] sub; // 保存结果 private List> result;

public List> solveNQueens(int n) {

  result = new ArrayList<>();
  if (n == 0) return result;
  // Global variables, reduce parameter passing
  this.n = n;
  this.col = new boolean[n];
  this.main = new boolean[2 * n - 1];
  this.sub = new boolean[2 * n - 1];
  // Replace Stack(which is Deprecated)
  Deque<Integer> track = new ArrayDeque<>();
  dfs(0, track);
  return result;

}

private void dfs(int row, Deque track) {

  if (row == n) {
      List<String> board = convert2board(track);
      result.add(board);
      return;
  }
  // Is [row, i] legal? 
  for (int i = 0; i < n; ++i) {
      if (!col[i] && !main[row - i + n - 1] && !sub[row + i]) {
          // put a queen into the board and update the status
          track.addLast(i);
          col[i] = true;
          sub[row + i] = true;
          main[row - i + n -1] = true;
          // next row
          dfs(row + 1, track);
          // Retrieve status
          track.removeLast();
          col[i] = false;
          sub[row + i] = false;
          main[row - i + n -1] = false;
      }
  }

}

private List convert2board(Deque track) {

  List<String> board = new ArrayList<>();
  for (int num : track) {
      StringBuilder row = new StringBuilder();
      row.append(".".repeat(n));
      row.replace(num, num + 1, "Q");
      board.add(row.toString());
  }
  return board;

}

也是逃不出框架，只是判断合法略复杂，需要同时考虑竖直方向与两条对角线方向的合法性。sub和main对角线的下标可以通过row，col，n得到。![](https://cdn.nlark.com/yuque/0/2020/png/1744194/1607587400058-05e5619a-7a02-4e1d-a31d-e30dbebbb4ee.png#align=left&display=inline&height=978&margin=%5Bobject%20Object%5D&originHeight=978&originWidth=2090&size=0&status=done&style=none&width=2090)<br />本题需要输出棋盘，所以需要一个convert方法，将track[row] = col的形式转成棋盘list。
<a name="4QI7E"></a>
## 解数独
```java
class Solution {

    // row[i][x-1] = false 第i行没有x
    private boolean[][] row = new boolean[9][9];
    // col[j][x-1] = false 第j列没有x
    private boolean[][] col = new boolean[9][9];
    // col[i/3][j/3][x-1] 这个block里面没有x
    private boolean[][][] block = new boolean[3][3][9];
    // 保存所有的空格[x, y]
    private List<int[]> spaces = new ArrayList<>();
    // 数独能否跑的通
    private boolean valid = false;

    public void solveSudoku(char[][] board) {
        // 准备工作，准备spaces和row，col，block
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') spaces.add(new int[]{i, j});
                else {
                    int digit = board[i][j] - '0' - 1;
                    row[i][digit] = col[j][digit] = block[i / 3][j / 3][digit] = true;
                }
            }
        }
        dfs(board, 0);
    }

    private void dfs(char[][] board, int pos) {
        // End of spaces
        if (pos == spaces.size()) {
            valid = true;
            return;
        }
        // 得到当前空位的[i, j]
        int[] space = spaces.get(pos);
        int i = space[0], j = space[1];
        // 遍历所有的取值。已经valid了就退出。
        for (int digit = 0; digit < 9 && !valid; ++digit) {
            if (!row[i][digit] && !col[j][digit] && !block[i / 3][j / 3][digit]) {
                // 做选择
                row[i][digit] = col[j][digit] = block[i / 3][j / 3][digit] = true;
                board[i][j] = (char)(digit + '0' + 1);
                // 下一步
                dfs(board, pos + 1);
                // 取消选择，因为board后续可以被其他值覆盖，所以不必恢复，如果恢复的话，由于判断完成的标准是
                // 跑完spaces里的空位，可能最后还会剩下空位没有填。
                row[i][digit] = col[j][digit] = block[i / 3][j / 3][digit] = false;
            }
        }
    }
}

可以将row, col, block数组优化成位运算，不用9个数字而是1个数字，即二进制表示为 (011000100)时，就表示数字 3，7，8 已经出现过。这样可以使它们降低一维。