作者：Rhythm_2019
创立工夫：2021.04.04
批改工夫：2021.04.05
Email：rhythm_2019@163.com
导读：本文次要讲述利用回溯算法生成数组的子集、组合和排列，三者都是在数组中一直做“抉择元素”、“递归”、“勾销抉择”三件事，依据题目的不同要求退出一些条件束缚（深度限度、判重）即可解决问题。文章最初总结了本人在写代码时所犯下的谬误，通过本文本人也对回溯算法有了信的了解
通过浏览本文您能够解答上面算法题：
- LeetCode78. 子集
- LeetCode90. 子集 II
- LeetCode77. 组合
- LeetCode46. 全排列
- LeeCode47. 全排列 II
当然啦，最重要的是你在写回溯代码的时候的那种感觉，我在写代码的时候犯了很多谬误，都放在文章的最初啦
<hr/>
咱们先回顾一下什么是递归，简略来说就是本人调用本人，为什么本人调用本人就能解决问题呢？是因为问题存在反复的子问题，而且规模放大到最小时问题的解是已知的。
不用将分治、递归、回溯华清界线，就当本人在写递归即可
上面是递归的模板
private void recursion(int level, int maxLevel, int param) { // Terminator // Process // Drill down // Restore}回溯算法其实就是再下探Drill down后对数据进行复原，也就是Restore，从而达到一直试探但成果。在平时的算法练习中我常写递归，然而须要回溯的状况比拟少（可能是我写的不多），比拟常见的就是走迷宫（DFS染色）、生成子集、N皇后、数独等
子集
数组[1, 2]的子集有[]、[1]、[2]、[1, 2]四个，大家重点注意一下回溯的解法，其余解法大家看看就好
LeetCode 78 子集
给定一个数组nums，生成其所有子集，我想到的思路有：
- 自顶向下：已知
[0, i]的所有子集，以后数字2能够抉择退出他们，抉择不退出他们，这样即可生成所有子集，咱们把这个办法称为抉择退出吧 - 对于任意元素都有两种抉择，呈现在汇合里，不呈现在汇合里，这样就能生成所有子集，这个办法称之为抉择呈现吧
- 回溯算法，别离对数组中的元素做选自、递归、勾销抉择
先是第一种抉择退出的思路
public List<List<Integer>> subsets(int[] nums) { if (nums.length == 0) { return new ArrayList<>(); } return _subsets(nums.length - 1, nums);}public List<List<Integer>> _subsets(int level, int[] nums) { // Terminator if (level < 0) { List<List<Integer>> ans = new ArrayList<>(); ans.add(new ArrayList<>()); return ans; } // Process & Drill dwon // 取得后面的所有子集 List<List<Integer>> subsets = _subsets(level - 1, nums); int size = subsets.size(); for (int i = 0; i < size; i++) { List<Integer> list = new ArrayList<>(subsets.get(i)); list.add(nums[level]); subsets.add(list); } return subsets;}第二种抉择呈现的思路
private List<List<Integer>> ans = new ArrayList<>();public List<List<Integer>> subsetsWithDup(int[] nums) { if (nums.length == 0) { return ans; } Arrays.sort(nums); _subsets(0, nums, new ArrayList<>(), new HashSet<>()); return ans;}public void _subsets(int level, int[] nums, ArrayList<Integer> list) { // Terminator if (level == nums.length) { ans.add(list); return; } // Process & Drill down ArrayList<Integer> list1 = (ArrayList<Integer>) list.clone(); ArrayList<Integer> list2 = (ArrayList<Integer>) list.clone(); // 呈现 list1.add(nums[level]); _subsets(level + 1, nums, list1, res); // 不呈现 _subsets(level + 1, nums, list2, res);}<hr/>
最初就是回溯算法，咱们应用循环别离对数组中的元素做抉择，调用递归函数，勾销抉择
private List<List<Integer>> ans = new ArrayList<>();private List<List<Integer>> subsets(int[] nums) { if (nums.length == 0) { return ans; } _subsets(0, nums, new ArrayList<>()); return ans;}private void _subsets(int level, int[] nums, ArrayList<Integer> list) { // 每一步都要保留后果 ans.add(new ArrayList<>(list)); for (int i = level; i < nums.length; i++) { // 【抉择】 list.add(nums[i]); // 【递归】 _subsets(i + 1, nums, list); // 【勾销抉择】 list.remove(level); }}将其状态树画进去，大略是这样子的。途中一行代表递归的层级，黄色示意须要被保留的后果
LeetCode 90 子集 II
我一开始以位间接加一个哈希表对反复元素进行剪枝即可，折腾了半天才发现问题
图上浅灰色方块示意应用哈希表剪枝的元素，比方最左边灰色的1因为和最后面的1反复了，咱们就不对他进行递归了。黄色示意后果，大家能够看到深灰色的两个元素反复了，这时因为蕴含反复元素，很天然的[1, 2]和[2, 1]是反复的只能保留一个
如果我对数组进行排序，问题就会失去解决
排序可能将反复元素放在一起，前面的元素就不会生成和后面数字相干的子集
private List<List<Integer>> ans = new ArrayList<>();public List<List<Integer>> subsetsWithDup(int[] nums) { if (nums.length == 0) { return ans; } Arrays.sort(nums); _subsets(0, nums, new ArrayList<>(), new HashSet<>()); return ans;}private void _subsets(int level, int[] nums, ArrayList<Integer> list, Set<Integer> visited) { ans.add(new ArrayList<>(list)); for (int i = level; i < nums.length; i++) { if (visited.contains(nums[i])) { continue; } visited.add(nums[i]); list.add(nums[i]); _subsets(i + 1, nums, list, new HashSet<>()); list.remove(level); }}这里介绍了回溯的办法，咱们也能够应用抉择呈现现的思路，不过也是须要先排序，而后计算反复元素个数，如果就一个，依照以前的逻辑兵分两路，如果超过n个(n > 1)，阐明存在反复元素，正确的逻辑应该是让数字呈现0 ~ n次
private List<List<Integer>> ans = new ArrayList<>();public List<List<Integer>> subsetsWithDup(int[] nums) { if (nums.length == 0) { return ans; } Arrays.sort(nums); _subsets(0, nums, new ArrayList<>(), new HashSet<>()); return ans;}private void _subsets(int level, int[] nums, ArrayList<Integer> list, Set<Integer> visited) { // Terminator if (level >= nums.length) { ans.add(list); return; } // Process & Drill down int count = 1, index = level + 1; while (index < nums.length && nums[level] == nums[index]) { index++; count++; } if (count == 1) { // 没有反复 ArrayList<Integer> list1 = (ArrayList<Integer>) list.clone(); ArrayList<Integer> list2 = (ArrayList<Integer>) list.clone(); // 呈现 list1.add(nums[level]); _subsets(level + 1, nums, list1, visited); // 不呈现 _subsets(level + 1, nums, list2, visited); } else { // 存在反复 ArrayList<Integer> list1 = (ArrayList<Integer>) list.clone(); // 不呈现 _subsets(level + count, nums, (ArrayList<Integer>) list1.clone(), visited); for (int i = 1; i <= count; i++) { list1.add(nums[level]); // 呈现i次 _subsets(level + count, nums, (ArrayList<Integer>) list1.clone(), visited); } }}组合
以前看动静布局的时候始终没弄明确排列和组合的区别，那题Coin Change i/ii历历在目。对于一个数组c长度为n，其组合有C（n, m）个，而排列数则有A(n, m)个
LeetCode 77 组合
子集蕴含所有组合的状况，入参k其实示意的是递归层数，所以咱们只须要在子集的根底上增加一个终止条件即可
private List<List<Integer>> ans = new ArrayList<>();public List<List<Integer>> combine(int n, int k) { if (n < 0) { return ans; } _combine(0, 1, n, k, new ArrayList<>()); return ans;}private void _combine(int level, int start, int n, int k, List<Integer> list) { if (level == k) { ans.add(list); return; } for (int i = start; i <= n - (k - list.size()) + 1; i++) { list.add(i); _combine(level + 1, i + 1, n, k, new ArrayList<>(list)); list.remove(level); }}大家看图
其实和子集的一毛一样，最左边灰色的3被剪枝的次要是因为他凑不到2个。
数组和数字的生成形式很相似，如果数组中存在反复元素置信大家都会解决了
不那么相干的题目还有：17. 电话号码的字母组合
排列
LeetCode 46 全排列
组合是子集的一部分，然而排列就不一样了，每次抉择都能选后面的元素但又不能选到本人，所以咱们能够创立一个哈希表来存储抉择过的元素（这里抉择保留其索引）
private List<List<Integer>> ans = new ArrayList<>();public List<List<Integer>> permute(int[] nums) { if (nums == null || nums.length == 0) { return new ArrayList<>(); } _permute(0,nums, new ArrayList<>(), new HashSet<>()); return ans;}private void _permute(int level, int[] nums, List<Integer> List, Set<Integer> visited) { if (level == nums.length) { ans.add(List); return; } for (int i = 0; i < nums.length; i++) { if (visited.contains(i)) { continue; } visited.add(i); List.add(nums[i]); _permute(level + 1, nums, new ArrayList<>(List), visited); List.remove(nums[i]); visited.remove(i); }}画一下图大略就是这样
LeetCode 47 全排列 II
当初蕴含反复元素，咱们能够再创立一个哈希表用于记录以后层已应用过的元素，这样反复的元素就被剪枝
private List<List<Integer>> ans = new ArrayList<>();public List<List<Integer>> permuteUnique(int[] nums) { if (nums == null || nums.length == 0) { return new ArrayList<>(); } Arrays.sort(nums); _permute(0,nums, new ArrayList<>(), new HashSet<>()); return ans;}private void _permute(int level, int[] nums, List<Integer> List, Set<Integer> indexVisited) { if (level == nums.length) { ans.add(List); return; } Set<Integer> contentVisited = new HashSet<>(); for (int i = 0; i < nums.length; i++) { if (indexVisited.contains(i) || contentVisited.contains(nums[i])) { continue; } contentVisited.add(nums[i]); indexVisited.add(i); List.add(nums[i]); _permute(level + 1, nums, new ArrayList<>(List), indexVisited); List.remove(level); indexVisited.remove(i); }}这里波及两个哈希表：
indexVisited：用来记录递归时走过的元素，他保障了下一次递归不再拜访某元素，作用于全局，须要被始终传递的contentVisited：用来保留某一层已遍历的元素，这样就能剪掉反复元素，作用域某一层级，所以不必传递
总结
这篇文章我大略写了两天，感觉还有些中央没说分明，我感觉要把算法思维正确的表达出来是一件不容易的事，还须要多加了解和练习。对于下面这几个题目其实套路都差不多
private void recursion() { // 终止条件，个别都是限定递归层数 // 循环做抉择 for (int i = start; i <= n; i++) { // 【抉择】 将后果放入数组 // 【递归】 Drill down // 【勾销抉择】 将抉择移出数组 }}总结一下须要留神的几个点：
咱们写
for循环的时候怎么写，应该从哪里开始到哪里完结：如果是子集和组合，为了不反复抉择本人之前抉择的元素，咱们应该指定开始下标，每进入一曾递归下标往后挪动。对于组合如果提米规定了输入组合的长度咱们能够适当剪枝。对于排列数，每次都能够选之前的元素，所以是从0开始
什么时候须要引入
HashSet判重：不蕴含反复元素：子集和组合是不须要的，因为通过开始下标咱们曾经排除了之前抉择过的元素。而排列数则须要记录递归路上抉择过的索引（元素值也能够），这样就不会反复选到之前选过的元素，这个哈希表须要全局应用，须要被传递
蕴含反复元素：咱们须要应用
HashSet对以后层的反复元素进行剪枝，这个哈希表只作用于以后层，不须要传递所以蕴含反复元素时须要应用哈希表，而排列数原本就肯定须要哈希表
- 对于后果
list的传递需不需要clome：当然须要，咱们最好应用构造方法创立新的，而且要留神创立的机会，肯定是创立后马上退出后果集，两头不能有任何add和remove操作 最初想说的是留神【抉择】和【撤销抉择】的形式，我已经是这样写的代码
private void _combine(int level, int start, int n, int k, List<Integer> list) { // ... for (int i = start; i <= n - (k - list.size()) + 1; i++) { list.add(i); _combine(level + 1, i + 1, n, k, new ArrayList<>(list)); // 留神这里 list.remove(new Integer(i)); }}这样写在元素不反复的状况下是没什么问题的，然而如果存在反复元素的话递归时会删掉第一个反复的元素，所以咱们间接这样写
list.add(i);_combine(level + 1, i + 1, n, k, new ArrayList<>(list));// 留神这里list.remove(level);这样删除元素才正确
<hr/>
我集体感觉算法挺有意思的，本人也听喜爱写题，细想一下可能是因为这些题目规模较小，但十分微妙，你的代码让计算机变得灵便，学习老本也不会太高，所以我更喜爱算法。
之前面试遇到的一个题目，如何正确计算0.3 / 0.2 ，曾经脱了很久了，前面会给大家带来告计算机的小数和高精算法的内容，还有十分神奇的卡特兰数，大家能够期待一下。