递归算法还能够解决的一个典型问题，是具有树形结构的问题，当我们发现一个问题与一个更小的问题之间存在递推的关系时，递归关系呈现出来的是一个树形结构

树形问题：分析问题时，发现解决问题的思路本质是一棵树的形状

  • 回溯算法是在树形图上的深度优先遍历
  • 回溯的产生是由于深度优先遍历的回退，造成了状态重置或撤销选项

解决回溯问题的第一步是画出树形图

回溯的本质是DFS，回溯只是DFS产生的现象

  • 本质上是遍历的算法，全程使用一份状态变量去搜索状态空间里的所有状态
  • 具有DFS的自叶子到根的特点

递归与回溯 - 图1

EG：

17. 电话号码的字母组合

递归与回溯 - 图2

“23”可以分解为如下的树形

递归与回溯 - 图3

得到以下分析：

设，digits代表数字字符串，s(digits)是digits所能代表的字母字符串,，letter( digits[i] ) 表示第 i 个数字能表示的所有字母

则有：

  • s( digits[0…n-1] )

= letter( digits[0] ) + s( digits[1…n-1] )

= letter( digits[0] ) + letter( digits[1] ) + s( digits[2…n-1] )

= ……

思路步骤：

  1. 每次从digits中取出一个数字字符，找到其对应的字母字符串并循环

  2. 以当前的字母字符串为基础，从digits中取出下一个数字字符，找出字母字符串，递归取出所有数字字符并将当前字符与之前的字符串进行拼接 (s( digits[0…n-1] ) = letter( digits[0] ) + s( digits[1…n-1] ))

  3. 直到构成的解 s 长度与digits长度相同 (因为有多少数字组成的每一个字母字符串就有多少位，因此只要s的长度等于digits的长度)，就说明完成了一个字母组合，存入list

  4. 递归上述步骤，直到所有第一个数字对应的字母字符串的所有字母组合完毕

  1. /**
  2.  * @Author: antigenMHC
  3.  * @Date: 2020/3/27 11:47
  4.  * @Version: 1.0
  5.  **/
  6. public class test {
  8.     public static void main(String[] args) {
  10.         List<String> strings = new Solution().letterCombinations("23");
  11.         for (String s : strings) {
  12.             System.out.println(s);
  13.         }
  14.     }
  16. }
  19. class Solution {
  21.     private String[] letterTable = new String[]{
  22.             "",      //0
  23.             "",      //1
  24.             "abc",   //2
  25.             "def",   //3
  26.             "ghi",   //4
  27.             "jkl",   //5
  28.             "mno",   //6
  29.             "pqrs",  //7
  30.             "tuv",   //8
  31.             "wxyz",  //9
  32.     };
  34.     private List<String> lists = new LinkedList<>();
  35.     //返回值为digits所能表示的所有字母字符串组成的list
  36.     public List<String> letterCombinations(String digits) {
  37.         find(digits, 0, "");
  39.         return lists;
  40.     }
  41.     //index表示每次处理的数字在数字字符串中的位置
  42.     //该函数每次处理一位数字！
  43.     //s表示index之前已经转换了的数字，即 s ( digits[0, index-1] )
  44.     //寻找和digits[index]匹配的字母字符串，获得 letter( digits[index] )
  45.     //s ( digits[0, index-1] ) + letter( digits[index] ) = s ( digits[0, index] ) 即得到了一个新解
  46.     private void find(String digits, int index, String s){
  48.         //到达digits末尾，生成一个字母字符串
  49.         if(s.length() == digits.length()) {
  50.             lists.add(s);
  51.             return;
  52.         }
  54.         char nowDigits = digits.charAt(index);   //获取对应数字字符
  55.         assert (nowDigits >= '2' && nowDigits <= '9');
  57.         String letters = letterTable[nowDigits-'0'];  //提取数字对应的字母字符串
  59.         //遍历digits对应的字符串，每次得到一个字母，然后继续向下搜索，找出其后后面所有数字的组合
  60.         for(int i=0; i<letters.length(); i++){
  62.             //s+letters.charAt(i), 基于当前字母组合继续向下寻找
  63.             //digits有多少数字，最终的每一个字母字符串就有多少位，因此只需要将数字对应的字母字符串中的每一个字母取出来，与前面的拼接，然后继续对下一个数字
  64.             //进行字母字符的求解即可
  65.             find(digits, index+1, s+letters.charAt(i));
  67.         }
  69.         return;
  70.     }
  71. }

上述代码画出图来可以很好地理解

通过递归调用来寻找答案的过程也称为回溯，回溯法是暴利解法的一个主要实现手段

从树的形状来看和结果来看，结果的个数大致为 3 (n为树深度)，所以时间复杂度为 O(2)

回溯算法能够处理的问题

1.排列问题

46. 全排列

递归与回溯 - 图4

排列 ( nums[0…n-1] ) = {取出一个数字} + 排列 ( nums[0…n-1 - 这个数字] )

排列问题中，元素之间是相互冲突的，因此需要判断和回溯(使用了一个元素并存入list中后，去掉这个元素，选择下一个元素)

  1. class Solution {
  3.     private List<List<Integer>> reList = new ArrayList<>();
  5.     //一个List<Integer>为一个排列
  6.     public List<List<Integer>> permute(int[] nums) {
  8.         if(nums.length==0) return reList;
  10.         find(nums, 0, new ArrayList<>());
  12.         return reList;
  13.     }
  15.     //index表示第index个元素，l表示保存了index个元素的排列
  16.     //当传进index+1时，l就获得一个index+1个元素的排列
  17.     private void find(int[] nums, int index, List<Integer> l){
  18.         //至多组成nums.length的长度的一个排列，当index==nums.length时说明生成了一个排列到l中
  19.         //保存l到reList
  20.         if(index == nums.length){
  21.             //保存当前生成的这个排列
  22.             reList.add(new ArrayList<>(l));
  23.             return;
  24.         }
  25.         //遍历每一个数字，找到需要添加的第index+1个数字
  26.         for(int i=0; i<nums.length; i++){
  27.             //l中不存在这个数字，则添加
  28.             if(!l.contains(nums[i])){
  29.                 l.add(nums[i]);
  30.                 find(nums, index+1, l);
  31.                 //在排列问题中，元素之间是相互冲突的，因此在回溯时需要对l所存的内容也进行回溯
  32.                 //回退一个元素，不然l中就始终存在nums[i]了,nums[i]会被重复使用
  33.                 //回溯状态和变量！
  34.                 l.remove(l.size()-1);
  35.             }
  36.         }
  37.         return;
  38.     }
  39. }

排列问题中：一个数字在不同排列中可以出现多次，因此每次递归 i 从0开始

2.组合问题

77. 组合

递归与回溯 - 图5

递归与回溯 - 图6

组合问题中：前一次被取用元素在下一次中不再取用

  1. class Solution {
  3.     private List<List<Integer>> reList = new ArrayList<>();
  4.     private List<Integer> tmp = new ArrayList<>();
  5.     private List<Boolean> used = new ArrayList<Boolean>();
  6.     private int pre = -1;
  8.     public List<List<Integer>> combine(int n, int k) {
  10.         if(k==0 || n==0) return reList;
  12.         List<Integer> list = new ArrayList<>();
  13.         for(int i=0; i<=n; i++){
  14.             list.add(i);
  15.             used.add(false);
  16.         }
  18.         find(list, k, 1);
  19.         return reList;
  20.     }
  22.     private void find(List<Integer> n, int k, int index){
  24.         if(tmp.size() == k){
  25.             reList.add(new ArrayList<>(tmp));
  26.             return;
  27.         }
  29.         //组合问题基本模板
  30.         for(int i=index; i<n.size(); i++){
  31.             tmp.add(n.get(i));
  32.             //前一个分支把第i个数及以前的数字的所有情况都考虑了进去，因此从i+1个元素开始考虑
  33.             find(n, k, i+1);
  34.             //回溯，探寻弹出的元素可以组成的其他组合
  35.             //回溯算法中基本上都要
  36.             pre = tmp.remove(tmp.size()-1);
  37.         }
  38.     }
  39. }

剪枝思想

递归与回溯 - 图7

对于n=4，k=2的情况而言，根本不需要去考虑取4，即最后一个元素的情况，因此可以尝试将取4的情况 “剪掉”

对于分析发现：

  • 每次循环，储存组合的list中还有 k-list.size()个空位

  • 所以 [i … n] 中至少要有 k-list.size() 个元素来填补list的空位，于是 i 如何求呢？

    • k-l.size() == 1时, i(最大) == n\ == n-1+1， [n…n]就有1个元素刚好填补
    • k-l.size() == 2时, i(最大)==n-1==n-2+1, [n-1…n] 就有2个元素刚好填补
    • k-l.size() == 3时, i(最大)==n-2==n-3+1, [n-2…n] 3个元素刚好填补
  • 于是推导得 i <= n-(k-l.size())+1 <= n，i 不能大于 n-(k-l.size())+1 ，会导致需要填补的元素变多，空位不足
  1. class Solution {
  3.     private List<List<Integer>> reList = new LinkedList<>();
  5.     public List<List<Integer>> combine(int n, int k) {
  7.         if(k==0 || n==0 || k>n) return reList;
  9.         find(n, new ArrayList<>(), k, 1);
  10.         return reList;
  11.     }
  13.     private void find(int n, List<Integer> l, int k, int start){
  15.         if(l.size() == k){
  16.             reList.add(new ArrayList<>(l));
  17.             return;
  18.         }
  19.         // i<=n-(k-l.size())+1 剪枝条件
  20.         // list中还有k-l.size()个空位
  21.         // 所以 [i .... n] 中至少要有 k-l.size() 个元素填补，因此问题为 i 取多少时[i .... n]有k-l.size() 个元素？
  22.         // k-l.size() == 1时, i(最大)==n==n-1+1， [n...n]就有1个元素刚好填补
  23.         // k-l.size() == 2时, i(最大)==n-1==n-2+1, [n-1...n] 就有2个元素刚好填补
  24.         // k-l.size() == 3时, i(最大)==n-2==n-3+1, [n-2...n] 3个元素刚好填补
  25.         //因此 i <= n-(k-l.size())+1 <= n
  26.         //i最大等于n-(k-l.size())+1，因为如果i比n-(k-l.size())+1还大的话，list中就没有足够的空位了
  27.         for(int i=start; i<=n-(k-l.size())+1; i++){
  28.             l.add(i);
  29.             //前一个分支把第i个数及以前的数字的所有情况都考虑了进去，因此从i+1个元素开始考虑
  30.             find(n, l, k, i+1);
  31.             l.remove(l.size()-1);
  32.         }
  33.     }
  34. }

39. 组合总和

递归与回溯 - 图8

  1. class Solution {
  3.     private Set<List<Integer>> set = new HashSet<>();
  4.     private List<List<Integer>> reList = new LinkedList<>();
  5.     private List<Integer> tmp = new ArrayList<>();
  7.     public List<List<Integer>> combinationSum(int[] candidates, int target) {
  9.         if(candidates.length == 0) return reList;
  11.         find(candidates, target, 0, 0);
  12.         reList.addAll(set);
  14.         return reList;
  15.     }
  17.     private void find(int[] candidates, int tartget, int index, int sum){
  18.         if(sum > tartget) return;
  19.         if(sum==tartget || index>candidates.length){
  20.             set.add(new ArrayList<>(tmp));
  21.             return;
  22.         }
  23.         //从index开始，每一位都重复添加，看是否与target相等
  24.         for(int i=index; i<candidates.length; i++){
  25.             tmp.add(candidates[i]);
  26.             //传入i，重复相加
  27.             find(candidates, tartget, i, sum+candidates[i]);
  28.             tmp.remove(tmp.size()-1);
  29.         }
  30.     }
  31. }

40. 组合总和 II

递归与回溯 - 图9

  1. class Solution {
  3.     private Set<List<Integer>> set = new HashSet<>();
  4.     private List<List<Integer>> reList = new LinkedList<>();
  5.     private List<Integer> tmp = new ArrayList<>();
  6.     private Set<Integer> canSet = new HashSet<>();
  7.     private int pre = -1;
  9.     public List<List<Integer>> combinationSum2(int[] candidates, int target) {
  11.         Arrays.sort(candidates);   //排序，相邻大小数挨在一起
  13.         find(candidates, target, 0, 0);
  14.         reList.addAll(set);
  16.         return reList;
  17.     }
  18.     //每个数只能选择一次, 不允许同级出现同样大小的元素，但不同层可以
  19.     private void find(int[] candidates, int tartget, int index, int sum){
  21.         if(sum > tartget) return;
  23.         if(sum==tartget){
  24.             set.add(new ArrayList<>(tmp));
  25.             return;
  26.         }
  28.         for(int i=index; i<candidates.length; i++){
  29.             //用pre记录删除了的元素，表示已经使用过，不再使用，剪枝
  30.             if(pre == candidates[i]) continue;
  32.             tmp.add(candidates[i]);
  33.             //一个数只能用一次，i+1
  34.             find(candidates, tartget, i+1, sum+candidates[i]);
  35.             pre = tmp.remove(tmp.size()-1);
  36.         }
  38.     }
  39. }

216. 组合总和 III

递归与回溯 - 图10

  1. class Solution {
  3.     private Set<List<Integer>> reSet = new HashSet<>();
  4.     private List<Integer> tmp = new ArrayList<>();
  5.     private int[] arr = new int[]{1,2,3,4,5,6,7,8,9};
  6.     private boolean[] used = new boolean[]{false,false,false,false,false,false,false,false,false};
  8.     public List<List<Integer>> combinationSum3(int k, int n) {
  10.         find(n,k,0, 0);
  12.         List<List<Integer>> reList = new ArrayList<>(reSet);
  13.         return reList;
  14.     }
  16.     private void find(int target, int k, int index, int sum){
  18.         if(sum > target || tmp.size() > k) return;
  19.         if(sum == target && tmp.size()==k){
  20.             reSet.add(new ArrayList<>(tmp));
  21.             return;
  22.         }
  24.         for(int i=index; i<9; i++){
  25.             if(!used[i]){
  26.                 tmp.add(arr[i]);
  27.                 used[i] = true;
  28.                 find(target, k, i, sum+arr[i]);
  29.                 used[i] = false;
  30.                 tmp.remove(tmp.size()-1);
  31.             }
  32.         }
  33.     }
  34. }

组合题规律总结

当题干包含：

  • 递归与回溯 - 图11时，使用Set集合去重

  • 递归与回溯 - 图12 使用辅助数字判断哪个数字已经被使用过，在生成一个组合后将数字和存储组合的列表回溯 (如216，面试题08)

  • 递归与回溯 - 图13循环时 i 以传入第index位基位，递归时重复传入当前 i 表示可以重复使用 (如39题)

  • 递归与回溯 - 图14循环时 i 以传入第index位基位，递归时传入 i+1，表示前 i 个数字已经存在当前组合中 (这种情况下可以考虑剪枝提高效率) (如40题)

二维平面上的回溯法

比如最常见的迷宫问题

79. 单词搜索

递归与回溯 - 图15

递归与回溯 - 图16

基于传入的坐标，对当前坐标的四周进行试探，当满足条件是进入坐标，继续试探，被试探过的坐标应该标记为visited，当该坐标四周试探完成不满足条件后，应该将vitised回溯为未访问状态，以便让其相邻位置进行试探

  1. class Solution {
  3.     //设置偏移量数组的技巧在二维数组问题中经常使用
  4.     //4个方位，每个一维数组中的第一个元素代表startX的移动，第二个元素代表startY的移动
  5.     private int map[][] = new int[][]{  {-1,0},   //上
  6.                                         {0,1},    //右
  7.                                         {1,0},    //下
  8.                                         {0,-1}};  //左
  9.     private Boolean[][] visited;
  11.     public boolean exist(char[][] board, String word) {
  13.         if(board.length==0 || word==null) return false;
  15.         visited  = new Boolean[board.length][board[0].length];
  17.         for(int i=0; i<board.length; i++){
  18.             for(int j=0; j<board[i].length; j++){
  19.                 visited[i][j] = false;
  20.             }
  21.         }
  23.         for(int i=0; i<board.length; i++){
  24.             for(int j=0; j<board[i].length; j++){
  25.                 //每次从[i][j]出发，寻找相应的字符串
  26.                 if (searchWord(board, word, 0, i, j)) {
  27.                     return true;
  28.                 }
  29.             }
  30.         }
  32.         return false;
  33.     }
  34.     //每次查找word的第index个元素
  35.     //从board[startX][startY]开始，寻找word[index...word.length()]
  36.     private boolean searchWord(char[][]board, String word, int index, int startX, int startY){
  38.         //当前所处的board位置是否与字符串最后一位相同
  39.         if(index == word.length()-1){
  40.             return board[startX][startY] == word.charAt(index);
  41.         }
  42.         //元素相等时，继续搜索
  43.         if(board[startX][startY] == word.charAt(index)){
  44.             //设置为已经访问过该元素
  45.             visited[startX][startY] = true;
  46.             //从startX，startY开始朝四个方向出发进行搜索
  47.             for(int i=0; i<4; i++){
  48.                 int newX = startX + map[i][0];
  49.                 int newY = startY + map[i][1];
  50.                 //newX,newY不能越界 && board[newX][newY]没有被访问过
  51.                 if((newX>=0 && newX<board.length && newY>=0 && newY<board[0].length) &&
  52.                         !visited[newX][newY]){
  53.                     if (searchWord(board, word, index+1, newX, newY)) {
  54.                         return true;
  55.                     }
  56.                 }
  57.             }
  58.             //基于[startX][startY]找遍4个方向都找不到的话，放弃[startX][startY]位置，置位false
  59.             visited[startX][startY] = false;
  60.         }
  61.         return false;
  62.     }
  63. }

FloodFill算法(洪泛填充算法)

FloodFill的过程其实就是 DFS 的过程

200. 岛屿数量

递归与回溯 - 图17

但我们需要找到与一个陆地直接相邻，即同属于一个岛屿的其它陆地(递归寻找)，进行标记，这样在寻找下一个岛屿的时候才不会重复。

从某个位置开始向外扩散，直到没有相连的陆地，这个过程就是FloodFill的过程

这里的 FloodFill算法 不需要进行状态回溯，因为当递归未结束时找到的所有陆地一定属于了一个岛屿，如果回溯了的话就说明不属于这个岛屿了

  1. class Solution {
  3.     private boolean[][] visited;
  4.     private int[][] map = new int[][]{{-1,0},{0,1},{1,0},{0,-1}};
  6.     private int islands;
  7.     public int numIslands(char[][] grid) {
  9.         if(grid.length==0) return 0;
  11.         visited = new boolean[grid.length][grid[0].length];
  12.         for (int i = 0; i < grid.length; i++) {
  13.             for(int j = 0; j < grid[i].length; j++){
  14.                 visited[i][j] = false;
  15.             }
  16.         }
  18.         for (int i = 0; i < grid.length; i++) {
  19.             for(int j = 0; j < grid[i].length; j++){
  20.                 //FloodFill ：本质就是一次DFS
  21.                 //递归终止条件隐含在这，只有陆地才会归入岛屿
  22.                 //再次循环时，对于同属于这块岛屿的其它陆地就不会再进行查找
  23.                 if(grid[i][j] == '1' && !visited[i][j]){
  24.                     islands++;
  25.                     findIslands(grid, i, j);
  26.                 }
  27.             }
  28.         }
  30.         return islands;
  31.     }
  33.     private void findIslands(char[][] grid, int startX, int startY){
  35.         for(int i=0; i<4 ;i++) {
  36.             //不仅标识是否被访问，同时也标识已经属于一个岛屿了
  37.             visited[startX][startY] = true;
  38.             int newX = startX+map[i][0];
  39.             int newY = startY+map[i][1];
  40.             if(newX>=0 && newX<grid.length && newY>=0 && newY<grid[0].length && !visited[newX][newY]){
  41.                 if(grid[newX][newY] == '1'){
  42.                     findIslands(grid, newX, newY);
  43.                 }
  44.             }
  45.             //这里不需要状态回溯，因为当递归未结束时找到的所有陆地一定属于了一个岛屿，如果回溯了的话就说明不属于这个岛屿了
  46.         }
  47.     }
  48. }

这里有另外一种更简洁的解法

  1. //思米马赛！
  2. //一次dfs找到一个岛屿
  3. class Solution {
  4.     public static void dfs(char[][] grid, int i, int j) {
  5.         if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != '1') return;
  6.         else grid[i][j] = '2';            // 将找到的 '1' 标注为 2，防止便利时再被找到
  7.         dfs(grid, i, j+1);                // 搜索上下左右的 '1'
  8.         dfs(grid, i-1, j);
  9.         dfs(grid, i+1, j);
  10.         dfs(grid, i, j-1);
  11.     }
  13.     public static int numIslands(char[][] grid) {
  14.         int count = 0;
  15.         for (int i = 0; i < grid.length; i++) {
  16.             for (int j = 0; j < grid[0].length; j++) {
  17.                 if(grid[i][j] == '1') {
  18.                     ++count;
  19.                     dfs(grid, i, j);
  20.                 }
  21.             }
  22.         }
  23.         return count;
  24.     }
  25. }

130. 被围绕的区域

递归与回溯 - 图18

只要与边界上的O相邻的所有O都不会被反转成X，因此可以认为是一个反向的FloodFill，从边界上的每一个O开始递归，将递归到的所有为O的位置标记为true (在对grid遍历时对于X的位置就可以标记为true)。最后将不为true的位置(即不与边界相连)上的所有元素转换成X

  1. class Solution {
  3.     int[][] map = new int[][]{{-1,0},{0,1},{1,0},{0,-1}};
  4.     boolean[][] visited;
  6.     public void solve(char[][] board) {
  8.         if(board.length == 0) return;
  10.         visited = new boolean[board.length][board[0].length];
  11.         for (int i = 0; i < board.length; i++) {
  12.             for(int j=0; j<board[i].length; j++){
  13.                 visited[i][j] = false;
  14.             }
  15.         }
  17.         //找出与边界相连的所有O,以及所有X，标记为true
  18.         for (int i = 0; i < board.length; i++) {
  19.             for(int j=0; j<board[i].length; j++){
  20.                 if(board[i][j]=='X') visited[i][j] = true;
  21.                 //从边界开始进行dfs
  22.                 if(board[i][j]=='O' && (i==0 || j==0 || i==board.length-1 || j==board[i].length-1)){
  23.                     dfs(board, i, j);
  24.                 }
  25.             }
  26.         }
  27.         //没有被标记的就是没有与边界相邻的O了
  28.         for (int i = 0; i < visited.length; i++) {
  29.             for(int j=0; j<visited[i].length; j++){
  30.                 if(!visited[i][j]){
  31.                     board[i][j] = 'X';
  32.                 }
  33.             }
  34.         }
  36.     }
  38.     public void dfs(char[][] board, int startX, int startY){
  40.         for(int i=0; i<4; i++){
  41.             visited[startX][startY] = true;
  42.             int newX = startX+map[i][0];
  43.             int newY = startY+map[i][1];
  45.             if(newX>0 && newY>0 && newX<board.length && newY<board[0].length && !visited[newX][newY]){
  46.                 if(board[newX][newY] == 'O'){
  47.                     dfs(board, newX, newY);
  48.                 }
  49.             }
  50.         }
  51.     }
  52. }

51. N皇后

递归与回溯 - 图19

递归与回溯 - 图20

递归与回溯 - 图21

以4皇后为例，4*4的范围，每一行都应该有一个皇后，不然其中一行没有皇后，则说明另外一行至少有两个皇后，即违背题意。

每一次在一行中摆放一个皇后，看是否能摆放，如果不能摆放则回到上一行，重新摆放上一行皇后的位置，直到在四行中每一行都摆放了皇后

递归与回溯 - 图22

对第二行而言，位置0和1是不满足条件的位置(和row1冲突)，于是剪枝剪去

于是，如何快速判断不合法情况？

  • 竖向：col[i] 表示第 i 列已经被占用
  • 对角线1：dia1[i] 表示对角线1中第 i 个元素被占用
  • 对角线2：dia2[i] 表示对角线2中第 i 个元素被占用

对对角线1而言

递归与回溯 - 图23

发现对角线上的横纵坐标相加是相同的，于是用dia1[x+y] 表示第 i 个对角线被占用很合适

对对角线2而言

递归与回溯 - 图24

对角线上的横纵坐标相减的值是一样的，但是由于是从-3开始的，于是使用 i-j+n-1使其从下标0开始，即 dia2[x-y+n-1]

class Solution {

    //存放每一行皇后摆放在第几列的位置
    //row[0] 存放 第一行中皇后所在的位置
    //row[1] 存放 第二行中皇后所在的位置
    private List<Integer> row = new ArrayList<>();
    //纵方向是否冲突
    private List<Boolean> col = new ArrayList<>();
    //两个对角线方向是否冲突
    private List<Boolean> dia1 = new ArrayList<>();
    private List<Boolean> dia2 = new ArrayList<>();

    private List<List<String>> reList = new ArrayList<>();
    //n皇后的一个解是一个字符串组成的大小为n的列表
    public List<List<String>> solveNQueens(int n) {

        for(int i=0; i<n; i++){
            col.add(false);
        }

        for(int i=0; i<2*n-1; i++){
            dia1.add(false);
            dia2.add(false);
        }

        find(n, 0);

        return reList;
    }
    //index: 第几行
    //在n皇后问题中，摆放第index行的皇后所处位置
    private void find(int n, int index){

        //index == n，说明得到了一个n皇后问题的解
        if(index == n){
            //增加一个n皇后问题的解，getOne生成一个.和Q组成的字符串列表
            reList.add(getOne(n));
            return;
        }

        for(int i=0; i<n; i++){
            //尝试将第index行的皇后摆放在第i列
            //如果在纵，以及两个对角线方向都不冲突的话，进行摆放
            if(!col.get(i) && !dia1.get(index+i) && !dia2.get(index-i+n-1) ){
                row.add(i);
                //将对应的列，及两个对角线置位true
                col.set(i, true);
                dia1.set(index+i, true);
                dia2.set(index-i+n-1, true);
                //尝试下一行
                find(n, index+1);
                //回溯
                col.set(i, false);
                dia1.set(index+i, false);
                dia2.set(index-i+n-1, false);
                row.remove(row.size()-1);
            }

        }
    }
    //将每一行转换为.，并在每一行的相应位置改为Q
    private List<String> getOne(int n){
        List<String> re = new ArrayList<>();
        //n*n的大小
        char[][] arr = new char[n][n];
        //每个位置初始化为.
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                arr[i][j] = '.';
            }
        }
        //在每一行的皇后位置置为Q
        for(int i=0; i<n; i++){
            //row代表每一行中的皇后应该存在的列位置
            arr[i][row.get(i)] = 'Q';
            //每一行形成的String存入re中
            re.add(String.valueOf(arr[i]));
        }
        return re;
    }
}