解决一个回溯问题，实际上就是一个决策树的遍历过程。你只需要思考 3 个问题：
1、路径：也就是已经做出的选择。
2、选择列表：也就是你当前可以做的选择。
3、结束条件：也就是到达决策树底层，无法再做选择的条件
如果你不理解这三个词语的解释，没关系，我们后面会用「全排列」和「N 皇后问题」这两个经典的回溯算法问题来帮你理解这些词语是什么意思，现在你先留着印象。
代码方面，回溯算法的框架：
# 一、全排列问题
46. 全排列
代码语言：javascript复制package com.zhanbo.backtracking;
import java.util.LinkedList;
import java.util.List;
/**
* @author zhanbo
* @version 1.0
* @describe 递归回溯全排列
* @date 2020/8/7-12:41
*/
public class FullArray {
/**
* 输入: [1,2,3]
* 输出:
* [
* [1,2,3],
* [1,3,2],
* [2,1,3],
* [2,3,1],
* [3,1,2],
* [3,2,1]
* ]
* @param nums
* @return
*/
List<List<Integer>> res = new LinkedList<>();
/* 主函数，输入一组不重复的数字，返回它们的全排列 */
List<List<Integer>> permute(int[] nums) {
// 记录「路径」
LinkedList<Integer> track = new LinkedList<>();
backtrack(nums, track);
return res;
}
// 路径：记录在 track 中
// 选择列表：nums 中不存在于 track 的那些元素
// 结束条件：nums 中的元素全都在 track 中出现
void backtrack(int[] nums, LinkedList<Integer> track) {
// 触发结束条件
if (track.size() == nums.length) {
res.add(new LinkedList(track));
return;
}
for (int i = 0; i < nums.length; i ) {
// 排除不合法的选择
if (track.contains(nums[i])) {
continue;
}
// 做选择
track.add(nums[i]);
// 进入下一层决策树
backtrack(nums, track);
// 取消选择
track.removeLast();
}
}
}
剑指 Offer 38. 字符串的排列
代码语言：javascript复制/**
*剑指offer38
*/
class Solution {
List<String> res = new LinkedList<>();
char[] c;
public String[] permutation(String s) {
c = s.toCharArray();
dfs(0);
return res.toArray(new String[res.size()]);
}
void dfs(int x) {
if(x == c.length - 1) {
// 添加排列方案
res.add(String.valueOf(c));
return;
}
HashSet<Character> set = new HashSet<>();
for(int i = x; i < c.length; i ) {
// 重复，因此剪枝
if(set.contains(c[i])) {
continue;
}
set.add(c[i]);
// 交换，将 c[i] 固定在第 x 位
swap(i, x);
// 开启固定第 x 1 位字符
dfs(x 1);
// 恢复交换
swap(i, x);
}
}
void swap(int a, int b) {
char tmp = c[a];
c[a] = c[b];
c[b] = tmp;
}
}
# 二、N 皇后问题
51. N皇后
