回溯：就是一个遍历决策树的过程

从八皇后问题说起

八皇后问题是一个古老的非常有意思的问题。时间退回到1848年，国际西洋棋棋手马克斯·贝瑟尔提出了这样的一个问题

在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问一共有多少种摆法。 此时我们就可以枚举所有的可能性，如下图为一个4皇后枚举的过程。 当然枚举的过程我们并不是想到啥就写啥，而是按照一定的规则，枚举所有的可能性。按照行和列依次递增来枚举所有的可能性。

第0行依次在第0，1，2，3列放第一个，接着放第二行。在枚举的过程中，如果我们发现目前的状态已经不符合要求时就没必要按照这种情况接着枚举了，这个技巧叫做剪枝

整个枚举的过程就如下图所示，这个树就叫决策树，演示了你枚举的整个流程。当然这个树是经过剪枝的，不然整个决策树会非常大，降低效率。 好了，我们开始枚举。记住我们需要一边枚举，一遍减枝。而不是等放完8个皇后，再看这8个皇后的放置合理不。

public class Solution {

    int sum = 0;

    public int solveNQueens(int n) {
    	// 存放每个皇后的位置
        int[] loc = new int[n];
        // 开始枚举
        backtracking(loc, n, 0);
        return sum;
    }
    
    /**
     * @param loc 存放皇后的位置
     * @param n 总共n个皇后
     * @param cur 当前应该放第cur个皇后，即放第cur行的皇后
     */
    public void backtracking(int[] loc, int n, int cur) {
        // n个皇后都放完了，算一种解法
        if (cur == n) {
            sum++;
            return;
        }
        for (int i = 0; i < n; i++) {
            boolean flag = true;
            // cur行的皇后放在第i列
            loc[cur] = i;
            // 检查是否和前面的皇后冲突
            for (int j = 0; j < cur; j++) {
                // 判断主对角线，副对角线，列是否重复
                if (cur - loc[cur] == j - loc[j] || cur + loc[cur] == j + loc[j]
                        || loc[cur] == loc[j]) {
                    // 和之前的皇后冲突了，重新放
                    flag = false;
                    break;
                }
            }
            // 符合要求，放下一行
            if (flag) {
                backtracking(loc, n, cur + 1);
            }
        }
    }
}

这里有个小技巧 cur - loc[cur] == j - loc[j] 判断主对角线是否重合 cur + loc[cur] == j + loc[j]判断副对角线是否重合 loc[cur] == loc[j] 判断列是否重合

我们是一行一行放的，所以列不会重合哈 可以看到我们每次判断主对角线，副对角线，列是否有皇后比较麻烦，我们能否这个状态给存下来呢？

看下图我们可以用x-y或者y-x来标识主对角线上已经有皇后了。用x+y标识副对角线上已经有皇后了

public class Solution {

    int sum = 0;

    public int solveNQueens(int n) {
        int[] loc = new int[n];
        // 用数组的第一维表示列，主对角线，副对角线
        int[][] visit = new int[3][2 * n];
        backtracking(loc, visit, n, 0);
        return sum;
    }

    public void backtracking(int[] loc, int[][] visit, int n, int cur) {
        if (cur == n) {
            sum++;
            return;
        }
        for (int i = 0; i < n; i++) {
            // 检查第cur行的第i列否和前面的皇后冲突
            // 判断列，判断主对角线（x-y有可能为负数所以加n），判断副对角线
            if (visit[0][i] != 1 && visit[1][cur - i + n] != 1 && visit[2][cur + i] != 1) {
                // cur行的皇后放在第i列，如果不用打印这个数组都可以省略
                loc[cur] = i;
                visit[0][i] = visit[1][cur - i + n] = visit[2][cur + i] = 1;
                backtracking(loc, visit, n, cur + 1);
                // 这一步一定要有，撤销选择
                visit[0][i] = visit[1][cur - i + n] = visit[2][cur + i] = 0;
            }
        }
    }
}

当数组对应的值为1时，说明有皇后了，否则没有皇后。 仔细和上面的代码对比，发现我们多了一个撤销选择的过程。如果我们不撤销自己的选择，会对后面的决策造成影响。

第2行第3列放完发现没有合适的位置，从第2行第4列开始放时，就要把你之前的决策回退，重新再来，就是悔棋。 我们最开始写的代码为什么没有回撤的过程呢？因为loc数组在运行的过程中会不断覆盖之前的选择，相当于隐式回撤了。

我们来总结一下回溯算法的套路，就是不断枚举的过程。

public void backtracking(决策树总共有n层, 当前选择到第cur层) {
    if (cur == n) {
        判断选择是否符合条件;
    }
    for (选择 : 第cur层的所有选择) {
        做选择;
        backtracking(n, cur + 1); // 接着到cur + 1层做选择
        撤销选择;
    }
}

组合/排列

知道了回溯算法的基本套路，再遇到回溯算法，很快就能解出来了。 回溯算法通常用来解决如下问题

1. 组合/排列
2. 去重的组合/排列
3. 子集

全排列

题目地址：LeetCode 46.全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

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

class Solution {

    List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> permute(int[] nums) {
        List<Integer> items = new ArrayList<>();
        backtracking(nums, items, 0);
        return result;
    }

    public void backtracking(int[] nums, List<Integer> items, int cur) {
        if (cur == nums.length) {
            result.add(new ArrayList<>(items));
        }
        for (int i = 0; i < nums.length; i++) {
            if (!items.contains(nums[i])) {
                items.add(nums[i]);
                backtracking(nums, items, cur + 1);
                items.remove(items.size() - 1);
            }
        }
    }
}

子集

题目地址：78. 子集

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

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

示例 1：

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

为了避免取到重复的子集合，我们用curIndex记录当前取了数组的第curIndex个元素，后续取的时候取后面的，这样就避免取到重复的子集，比如（1，3）和（3，1）

class Solution {

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> resultList = new ArrayList<>();
        resultList.add(new ArrayList<>());
        backtracking(resultList, new ArrayList<>(), nums, 0, 0);
        return resultList;
    }

    public void backtracking(List<List<Integer>> resultList, List<Integer> curList, int[] nums, int curIndex, int numIndex) {
        if (curIndex == nums.length) {
            return;
        }
        for (int i = numIndex; i < nums.length; i++) {
            curList.add(curIndex, nums[i]);
            resultList.add(new ArrayList<>(curList));
            backtracking(resultList, curList, nums,  curIndex + 1, i + 1);
            curList.remove(curIndex);
        }
    }
}