算法 07，递归回溯算法 - 排列、组合、子集、N 皇后、数独等。

回溯是一类特殊的递归算法，我们在算法篇05、二叉树相关算法那一篇中大量使用了递归算法，这一篇讲的回溯算法也是一类递归的算法，其实其本质就是n叉树的递归问题；典型的回溯算法就是求排列、组合、子集，以及大名鼎鼎的N皇后和数独问题等；

1、leetcode 46--全排列

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

题解如下所示，首先是递归终止条件，当list中元素个数和nums数组的个数相同时说明是其中一个排列结果，将结果放入List<List>中，这里注意一点应该新建一个List，因为传入的list是个引用，如果直接使用，最后存入的所有list就是同一个了；

递归过程其实就是多叉树的递归过程，开一个for循环，循环遍历数组中的元素，然后在循环中递归调用自身，因为全排列不能有重复元素，因此如果list中已经包含了当前遍历到的元素，就continue继续下一次循环；看，这不就是一棵n叉树的递归吗~n是数组的长度，只不过在递归过程中去除了重复元素而已；还有一点需要注意，在递归前后元素分别进入list和移除list，这是因为递归完此元素包含的分支之后应该将该元素移除，继续下一个元素的递归；

//leetcode 46 全排列
List<List<Integer>> res46 = new ArrayList<>();

public List<List<Integer>> permute(int[] nums) {
    if (nums == null || nums.length == 0) {
        return res46;
    }
    LinkedList<Integer> list = new LinkedList<>();
    generatePermutation(nums, list);
    return res46;
}

private void generatePermutation(int[] nums, LinkedList<Integer> list) {
	//递归终止条件，list中元素个数和nums数组的个数相同时说明是其中一个结果
	//在添加时为什么要new LinkedList<>，而不是直接传入list，因为这里的list是一个引用，如果传list，那么最后所有的list都是相同的；
    if (list.size() == nums.length) {
        res46.add(new LinkedList<>(list));
        return;
    }

    //递归调用过程，其实原理就是多叉树的递归
    for (int i = 0; i < nums.length; i++) {
        if (list.contains(nums[i])){
            continue;
        }else {
            list.addLast(nums[i]);
            generatePermutation(nums, list);
            list.removeLast();
        }
    }
}

2、leetcode 77--组合

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

示例:

输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

题解如下所示，组合跟排列的解题逻辑基本一致，首先是递归终止条件，当list中的元素个数等于k时表示是一种组合结果，然后放入总的结果中，这里同样注意不要直接传入list，而是要新建一个list；

递归过程也是多叉树的递归过程，开一个for循环遍历从start到n，start是我们传入的一个开始索引，因为组合中的元素也是不能重复的，因此在递归过程中开始索引传入start+1即可；递归前后元素进入list和元素移除list的逻辑和排列完全相同，这也是回溯算法的标准逻辑过程；

//leetcode 77 组合
List<List<Integer>> res77 = new LinkedList<>();

public List<List<Integer>> combine(int n, int k) {
    LinkedList<Integer> list = new LinkedList<>();
    backtrackCombination(n, k, 1, list);
    return res77;
}

private void backtrackCombination(int n, int k, int start, LinkedList<Integer> list) {
    if (list.size() == k) {
        res77.add(new LinkedList<>(list));
        return;
    }

    for (int i = start; i <= n; i++) {
        list.addLast(i);
        backtrackCombination(n, k, start + 1, list);
        list.removeLast();
    }
}

3、leetcode 78--子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

题解如下所示，理解了排列和组合的逻辑之后，再来理解子集问题就比较简单了，其实都是相同的一类逻辑，n叉树的递归；

这里主要注意两点，第一点还是在加入list时不要传入list，应该新建一个list；第二点就是开始因子start，这里跟组合不同，这里开始因子应该从0开始，因为空集也是子集并且数组索引从0开始的，而且递归过程中传入的start是i+1而不是start+1，传start+1会出现很多重复的元素；

//leetcode 78 子集
List<List<Integer>> res78 = new LinkedList<>();

public List<List<Integer>> subsets(int[] nums) {
    if (nums == null || nums.length == 0) {
        return res78;
    }
    LinkedList<Integer> temp = new LinkedList<>();
    subsets(nums, 0, temp);
    return res78;
}

private void subsets(int[] nums, int start, LinkedList<Integer> temp) {
    res78.add(new LinkedList<>(temp));

    for (int i = start; i < nums.length; i++) {
        temp.addLast(nums[i]);
        subsets(nums, i + 1, temp);
        temp.removeLast();
    }
}

4、leetcode 51--N皇后

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

题解如下所示，这里同样需要一个开始位置因子，这里的开始因子表示行row，下面可以看到递归的时候也是row+1递归下一行；递归终止条件就是row == chess.length，这表示chess这个二维数组中已经有一种皇后摆放的结果了，然后我们可以把这个结果放入总结果中，这里放入的时候采用了一点小技巧，将chess[][]二维数组转变为list集合；

递归过程就是开一个for循环遍历每一行中的所有列，然后在循环中递归调用下一行；这里最关键的逻辑是isValid(char[][] chess, int row, int col)这个函数，它用来判断chess二维数组中当前row行和col列是否可以摆放皇后Q，按照题目要求，需要不同行、不同列、不能在同一对角线上，因为我们是一行一行递归的，因此行不需要判断；列只需要判断上方，因为下方还没有递归到；对角线同样只需要判断上方的对角线，下方的也没有递归到，但又分为左上对角线和右上对角线两种情况；总共就这三种情况，代码中都有注释；

//leetcode 51 N皇后 大名鼎鼎的N皇后问题，做哭了快
List<List<String>> res51 = new LinkedList<>();

public List<List<String>> solveNQueens(int n) {
    //新建一个棋盘
    char[][] chess = new char[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            chess[i][j] = '.';
        }
    }
    traceBackQueue(chess, 0);
    return res51;
}

private void traceBackQueue(char[][] chess, int row) {
    if (row == chess.length) {
        res51.add(generateList(chess));
        return;
    }

    for (int col = 0; col < chess.length; col++) {
        if (isValid(chess, row, col)) {
            chess[row][col] = 'Q';
            traceBackQueue(chess, row + 1);
            chess[row][col] = '.';
        }
    }
}

private boolean isValid(char[][] chess, int row, int col) {
    //上方的列有皇后攻击，下方不用判断，因为下方还没有递归到
    for (int i = 0; i < row; i++) {
        if (chess[i][col] == 'Q') {
            return false;
        }
    }

    //左上对角线有皇后攻击
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (chess[i][j] == 'Q') {
            return false;
        }
    }

    //右上对角线有皇后攻击
    for (int i = row - 1, j = col + 1; i >= 0 && j < chess.length; i--, j++) {
        if (chess[i][j] == 'Q') {
            return false;
        }
    }

    return true;
}

//将二维数组char[][]转换为List
private List<String> generateList(char[][] chess) {
    List<String> result = new LinkedList<>();
    for (int i = 0; i < chess.length; i++) {
        result.add(new String(chess[i]));
    }
    return result;
}

5、leetcode 37--解数独

编写一个程序，通过填充空格来解决数独问题。

数独的解法需遵循如下规则：

数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图） 数独部分空格内已填入了数字，空白格用 '.' 表示。

来源：力扣（LeetCode） 链接：leetcode-cn.com/problems/su…

题解如下所示，我们可以把解数独问题类比成n皇后问题中的n等于9的情况，也就是9皇后；不同的是9皇后问题需要求出所有的解，但数独问题只需要一个解即可，因此求出一个解之后就可以直接返回，我们在代码也详细注释了；

//leetcode 37 解数独
public void solveSudoku(char[][] board) {
	//从board二维数组的0行0列开始递归回溯
    backTrack(board, 0, 0);
}

private boolean backTrack(char[][] board, int row, int col) {
    int m = 9, n = 9;
    //当遍历完某一行之后，继续去下一行递归
    if (col == n) {
        return backTrack(board, row + 1, 0);
    }
    //表示所有行都递归完了，因为只需要一个结果，直接返回true
    if (row == m) {
        return true;
    }
    //如果位置上的元素不是 . ,说明有预置的元素，不需要我们填写，直接递归下一个位置
    //我们递归的顺序是一行一行的递归，所以下一个位置是本行的下一列，也就是col+1
    if (board[row][col] != '.') {
        return backTrack(board, row, col + 1);
    }

    for (char ch = '1'; ch <= '9'; ch++) {
    	//如果此位置填写ch字符不合法，那么就continue下一次循环
        if (!isValidChar(board, row, col, ch)) {
            continue;
        }
        board[row][col] = ch;
        //因为数独只需要一个结果即可，所有产生一个结果就直接返回true
        if (backTrack(board, row, col + 1)) {
            return true;
        }
        board[row][col] = '.';
    }

    return false;
}

//判断是否可以在board二维数组的row行、col列摆放ch字符；
private boolean isValidChar(char[][] board, int row, int col, char ch) {
    for (int i = 0; i < 9; i++) {
    	//此分支表示同一行存在重复元素
        if (board[row][i] == ch) {
            return false;
        }
        //此分支表示同一列存在重复元素
        if (board[i][col] == ch) {
            return false;
        }
        //此分支表示3*3的方格内存在重复元素
        if (board[(row / 3) * 3 + i / 3][(col / 3) * 3 + i % 3] == ch) {
            return false;
        }
    }
    //所有限制条件都没有满足，返回true
    return true;
}

题目来源出处：

来源：力扣（LeetCode） 链接：leetcode-cn.com/problemset/…