1 模板
举个例子：输出一串数字[1,2,3]的全排列[1,2,3]，[1,3,2]，[2,1,3]，[2,3,1]，[3,1,2]，[3,2,1]。
这个问题交给人类来解决的话肯定是先固定第一位为 1，然后第二位可以是 2，那么第三位只能是 3；然后可以把第二位变成 3，第三位就只能是 2 了；然后就只能变化第一位，变成 2，然后再穷举后两位，以此类推......
就像下面这样的一个树形结构：
当我们停留在每一个 节点上时，都需要做一个决策，例如停留在图中红色节点上时，有[1, 3]两个数字可以做选择，如果选择了1之后再选择数字3（最后一个数字只有一个选项），则已经找到了一个不重复的数字，这一次的选择就结束了，我们会退回红色的节点继续向右子树搜索，以此类推......直到找到左右的结果。
这其实就是回溯算法，中学的时候就已经不自觉地掌握了。我们可以抽象一点，把整个算法的解决模板给概括出来，即：
解决一个回溯问题，实际上就是一个决策树的遍历过程，确定了以下三个条件，问题就迎刃而解了：
1.路径：已经做出的选择
2.选择列表：当前可以做的选择
3.结束条件（递归出口）：到达决策的底层，没有选择可做的条件
伪代码如下：
List<T> result = new ArrayList<>(); private void backtrack(路径, 选择列表){ if(满足结束条件){ result.add(路径); return; } for(选择 : 选择列表){ 做选择; backtrack(路径, 选择列表); 撤销选择; } }
上面蓝色文字“决策”对应的就是代码中的“做选择”，“结束”对应“满足结束条件”，“退回”对应“撤销选择”
其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」，特别简单。
多说无益，上例子。
2 排列组合问题
2.1 leetcode 77 组合
评论区里面的图画的已经非常直观了，我这里直接引用一下
根据我上面给的三个条件，将其对应在本题中如下：
1.路径：就是图中红色方块部分，当然树干上面“取X”也是路径
2.选择列表：就是图中蓝色方块部分
3.结束条件：路径中包含k个数字时。
我们定义的函数其实就像是一个指针，将这棵树的所有节点都走一遍之后整个程序就执行完毕了，所得的结果就是正确结果。如何将这棵树所有的节点都走一遍？其实就是前序遍历，中序遍历，后序遍历：
private traverse(TreeNode root){ for(TreeNode child : root.children){ traverse(child); } }
我们做选择以及撤销选择的动作正是在前序和后序的时间点做出的，即做了一个选择之后到下一个节点，将做的选择撤销以后回到上一个节点！
所以回溯算法的核心框架：
for(选择 : 选择列表){ // 做选择 将被选的项从候选表中删除; 路径.add(选择); backtrack(路径, 选择列表); // 撤销选择 路径.remove(选择); 重新将被选的项加入候选表; }
我们只要在递归之前做出选择，在递归之后撤销刚才的选择，就能正确得到每个节点的选择列表和路径。
本题解决方案如下：
class Solution { private List<List<Integer>> result = new ArrayList<>(); // 用一个栈来记录每一个组合 private void findCombinations(int n, int k, int begin, Stack<Integer> pre){ if(pre.size() == k){ result.add(new ArrayList<>(pre)); return; } for(int i = begin; i <= n; i ++){ pre.push(i); findCombinations(n, k, i + 1, pre); // 从下一个数字开始取 // 当前数字的情况已经全部取完，弹出栈顶元素 pre.pop(); } } public List<List<Integer>> combine(int n, int k) { if (n <= 0 || k <= 0 || n < k) { return result; } findCombinations(n, k, 1, new Stack<>()); return result; } }
这一部分就是递归出口（可以结合题意理解，我们只要找到k个数字就好）
每一个数字 i 就是要做的选择
返回用一个List来存储（当然其他的数据结构都可以~）
撤销选择操作，其实就是做选择的逆动作
2.2 leetcode 216 组合总和III
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
这种找出总和为某数字的问题，套路也很固定，只需在回溯函数里多添加一个遍历target用于记录求和的目标是多少即可。
class Solution { private List<List<Integer>> result = new ArrayList<>(); private List<Integer> temp = new ArrayList<>(); public List<List<Integer>> combinationSum3(int k, int n) { dfs(k, n, 1); return result; } private void dfs(int k, int sum, int start){ if(k == 0 && sum == 0){ // 符合条件 result.add(new ArrayList<>(temp)); // 注意深拷贝和浅拷贝！！必须是new一个新数组 return; } if(k == 0 || sum < 0) return; // 不符合条件 for(int i = start; i <= 9; i ++){ temp.add(i); dfs(k - 1, sum - i, i + 1); temp.remove(temp.size() - 1); // 回溯 } return; } }
2.3 leetcode 60 组合总和III
给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123"
"132"
"213"
"231"
"312"
"321"
给定 n 和 k，返回第 k 个排列。
leetcode上面的一个题解很优秀，这里引用一下。
public String getPermutation(int n, int k) { int[] nums = new int[n];//生成nums数组 for (int i = 0; i < n; i++){ nums[i] = i + 1; } boolean[] used = new boolean[n];//记录当前的索引的数是否被使用过 return dfs(nums, new ArrayList<String>(), used, 0, n, k); } /** * @param nums 源数组 * @param levelList 每一层的选择 * @param used 数组的元素是否被使用过 * @param depth 深度，也就是当前使用的元素的索引 * @param n 上限值 * @param k 第k个 * @return 第k个排列 */ private String dfs(int[] nums, List<String> levelList, boolean[] used, int depth, int n, int k) { if (depth == n) {//触发出口条件，开始收集结果集 StringBuilder res = new StringBuilder(); for (String s : levelList){ res.append(s); } return res.toString(); } int cur = factorial(n - depth - 1);//当前的depth也就是索引，有多少排列数 for (int i = 0; i < n; i++) { if (used[i]) continue;//当前元素被使用过，做剪枝 if (cur < k) {//当前的排列组合数小于k，说明就算这一层排完了，也到不了第k个，剪枝 k -= cur; continue; } levelList.add(nums[i] + "");//list收的是string类型 used[i] = true;//当前元素被使用过标记 return dfs(nums, levelList, used, depth + 1, n, k); } return null; } //返回n的阶乘，如3!=3*2*1=6 private int factorial(int n) { int res = 1; while (n > 0) { res *= n--; } return res; }
2.4 全排列II
给定一个可包含重复数字的序列，返回所有不重复的全排列。
涉及到去重的问题，一般思路都是将候选数组进行排序，然后再做一系列操作。这里我们选择对原数组排序，保证相同的数字都相邻，然后每次填入的数一定是这个数所在重复数集合中「从左往右第一个未被填过的数字」，即如下的判断条件：
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) { continue; }
详细代码如下：
class Solution { private boolean[] used; private List<List<Integer>> result; public List<List<Integer>> permuteUnique(int[] nums) { used = new boolean[nums.length]; result = new ArrayList<>(); Arrays.sort(nums); backtrack(nums, new ArrayList<>(), 0); return result; } private void backtrack(int[] nums, List<Integer> path, int index){ if(index >= nums.length){ result.add(new ArrayList<Integer>(path)); return; } for(int i = 0; i < nums.length; i ++){ if(used[i]){ continue; } // 只使用重复数字的第一个 // !used[i - 1] 说明当前重复数字左边还有未使用过的 if(i > 0 && nums[i] == nums[i - 1] && !used[i - 1]){ continue; } path.add(nums[i]); used[i] = true; backtrack(nums, path, index + 1); // 回溯 used[i] = false; path.remove(path.size() - 1); } } }
3 子序列问题
当然排列组合问题当然不仅限于全排列问题，还有可能让我们从候选项中选出一些元素出来，就是所谓的求子序列。
leetcode 1079 活字印刷
你有一套活字字模 tiles，其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。
注意：本题中，每个活字字模只能使用一次。
示例 1：
输入："AAB"
输出：8
解释：可能的序列为 "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA"。
同样是明确三个条件：
1.路径：同上题，先前已经选择的字母组成的字符串。
2.选择列表：剩下可供选择的字母，即 title 中除了被用掉的字母之外的所有字母
3.结束条件：由于每一个结果的长度不是固定的，而且我们只需要统计个数，所以在生成"AA"的途中我们必然会经过"A"，这是计数器也要进行累加。
这个题目算是比较特殊的，只用统计最后子序列的个数，所以在递归调用时不需要再传入路径和选择列表，不过在分析问题的时候还是要明确这两个概念，这样才不至于代码出错。
参考代码：
class Solution { int result = 0; public int numTilePossibilities(String tiles) { char[] counter = new char[26]; for(int i = 0; i < tiles.length(); i ++){ counter[tiles.charAt(i) - 'A'] ++; } backtrack(counter); return result; } private void backtrack(char[] counter){ for(int i = 0; i < 26; i ++){ // 剪枝，即排除无效选择 if(counter[i] == 0) continue; // 进行一次具体选择，本题就是 i 计数器减 1 counter[i] --; // 一次有效枚举，总的计数器加 1 result ++; // 继续回溯：递归 + 选择（尽可能剪枝） + 回退之前的现场恢复 backtrack(counter); // 回退之前，也就是进入另一分支之前，恢复当前分支的改动 counter[i] ++; } } }
由于并不需要输出最后得结果，所以只用将每个字母出现的频率统计出来就好（所幸英文字母的数量是可数的）。
一个选择就是选了一个字母，相应的频率减一就ok。
撤销选择就是将刚刚选择的字母重新放回候选列表中，即相应的字母频率加一。
4 子序列问题2
上面的问题其实是讨巧的，英文单词个数只有26个，并且只用输出序列的个数就可以了。如果将字母换做数字，那么就还是要老老实实地按照回溯的流程去做。
leetcode 面试题 08.04 幂集
幂集。编写一种方法，返回某集合的所有子集。集合中不包含重复的元素。
说明：解集不能包含重复的子集。
分析的三个条件和上题类似，只不过是将字母变作数字。
由于是子序列，所以我们在从 0 到 length - 1 遍历候选数组时有一些数字是可以不选的，因此就会在递归调用时产生分叉，只需多考虑一种情况即可。
class Solution { List<List<Integer>> result = new ArrayList<>(); List<Integer> temp = new ArrayList<>(); public List<List<Integer>> subsets(int[] nums) { dfs(nums, 0); return result; } private void dfs(int[] nums, int index){ if(index >= nums.length){ result.add(new ArrayList<>(temp)); // 注意浅拷贝 return; } // 不选择当前数字 dfs(nums, index + 1); // 选择当前数字 temp.add(nums[index]); dfs(nums, index + 1); // 回溯 temp.remove(temp.size() - 1); } }
当遍历数组的索引值超出数组范围时就是返回条件：
有两种情况需要考虑：选择当前数字 / 不选当前数字 ：
如果选择了当前数字的话就需要在结果集temp中进行添加
撤销选择操作就是将刚刚选择的数字从路径中删除即可：
5 24点游戏
leetcode 679 24点游戏
一共有 4 个数和 3 个运算操作，因此可能性非常有限。一共有多少种可能性呢？
首先从 4 个数字中有序地选出 2 个数字，共有 4×3=12 种选法，并选择加、减、乘、除 4 种运算操作之一，用得到的结果取代选出的 2 个数字，剩下 3 个数字。
实现时，有一些细节需要注意。
除法运算为实数除法，因此结果为浮点数，列表中存储的数字也都是浮点数。在判断结果是否等于 24 时应考虑精度误差，这道题中，误差小于 10^{-6}可以认为是相等。
进行除法运算时，除数不能为 0，如果遇到除数为 0 的情况，则这种可能性可以直接排除。由于列表中存储的数字是浮点数，因此判断除数是否为 0 时应考虑精度误差，这道题中，当一个数字的绝对值小于 10^{-6}时，可以认为该数字等于 0。
一共有 4 个数和 3 个运算操作，因此可能性非常有限。
首先从 4 个数字中有序地选出 2 个数字，共有 4×3=12 种选法，并选择加、减、乘、除 4 种运算操作之一，用得到的结果取代选出的 2 个数字，剩下 3 个数字。
实现时，有一些细节需要注意。
除法运算为实数除法，因此结果为浮点数，列表中存储的数字也都是浮点数。在判断结果是否等于 24 时应考虑精度误差，这道题中，误差小于 10^{-6}可以认为是相等。
进行除法运算时，除数不能为 0，如果遇到除数为 0 的情况，则这种可能性可以直接排除。由于列表中存储的数字是浮点数，因此判断除数是否为 0 时应考虑精度误差，这道题中，当一个数字的绝对值小于 10^{-6}时，可以认为该数字等于 0。
class Solution { static final int ADD = 0, MULTIPLY = 1, SUBTRACT = 2, DIVIDE = 3; public boolean judgePoint24(int[] nums) { List<Double> list = new ArrayList<Double>(); for (int num : nums) { list.add((double) num); } return backtrack(list); } public boolean backtrack(List<Double> list) { if (list.size() == 0) { return false; } if (list.size() == 1) { return Math.abs(list.get(0) - 24) < 1e-6; } int size = list.size(); for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { if (i != j) { // 选出来i，j这两个位置的数字做四则运算 List<Double> list2 = new ArrayList<Double>(); for (int k = 0; k < size; k++) { if (k != i && k != j) { // 剩下的数字保持不变 list2.add(list.get(k)); } } for (int k = 0; k < 4; k++) { if (k == ADD) { // 加法 list2.add(list.get(i) + list.get(j)); } else if (k == MULTIPLY) { // 乘法 list2.add(list.get(i) * list.get(j)); } else if (k == SUBTRACT) { // 减法 list2.add(list.get(i) - list.get(j)); } else if (k == DIVIDE) { // 除法 if (Math.abs(list.get(j)) < 1e-6) { // 分母不能为0 continue; } else { list2.add(list.get(i) / list.get(j)); } } if (backtrack(list2)) { return true; } // 回溯 list2.remove(list2.size() - 1); } } } } return false; } }
