一文读懂全部排列、组合和子集问题
前言
Hello，大家好，我是bigsai，long time no see！在刷题和面试过程中，我们经常遇到一些排列组合类的问题，而全排列、组合、子集等问题更是非常经典问题。本篇文章就带你彻底搞懂全排列！
求全排列？
全排列即：n个元素取n个元素(所有元素)的所有排列组合情况。
求组合？
组合即：n个元素取m个元素的所有组合情况(非排列)。
求子集？
子集即：n个元素的所有子集(所有可能的组合情况)。
总的来说全排列数值个数是所有元素，不同的是排列顺序；而组合是选取固定个数的组合情况(不看排列)；子集是对组合拓展，所有可能的组合情况(同不考虑排列)。
当然，这三种问题，有相似之处又略有所不同，我们接触到的全排列可能更多，所以你可以把组合和子集问题认为是全排列的拓展变形。且问题可能会遇到待处理字符是否有重复的情况。采取不同的策略去去重也是相当关键和重要的！在各个问题的具体求解上方法可能不少，在全排列上最流行的就是邻里互换法和回溯法，而其他的组合和子集问题是经典回溯问题。而本篇最重要和基础的就是要掌握这两种方法实现的无重复全排列，其他的都是基于这个进行变换和拓展。
全排列问题
全排列，元素总数为最大，不同是排列的顺序。
无重复序列的全排列
这个问题刚好在力扣46题是原题的，大家学完可以去a试试。
问题描述：
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例：
输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
回溯法实现无重复全排列
回溯算法用来解决搜索问题，而全排列刚好也是一种搜索问题，先回顾一下什么是回溯算法：
回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径.
而全排列刚好可以使用试探的方法去枚举所有中可能性。一个长度为n的序列或者集合。它的所有排列组合的可能性共有n！种。具体的试探策略如下：
- 从待选集合中选取第一个元素(共有n种情况)，并标记该元素已经被使用不能再使用。
- 在步骤1的基础上进行递归到下一层，从剩余n-1个元素中按照1的方法找到一个元素并标记，继续向下递归。
- 当所有元素被标记后，顺序收集被标记的元素存储到结果中，当前层递归结束，回到上一层(同时将当前层标记的元素清除标记)。这样一直执行到最后。
回溯的流程如果从伪代码流程大致为这样：
递归函数： 如果集合所有元素被标记： 将临时储存添加到结果集中 否则： 从集合中未标记的元素中选取一个存储到临时集合中 标记该元素被使用 下一层递归函数 (这层递归结束)标记该元素未被使用
如果用序列 1 2 3 4来表示这么回溯的一个过程，可以用这张图来显示：
用代码来实现思路也是比较多的，需要一个List去存储临时结果是很有必要的，但是对于原集合我们标记也有两种处理思路，第一种是使用List存储集合，使用过就移除然后递归下一层，递归完毕后再添加到原来位置。另一种思路就是使用固定数组存储，使用过对应位置使用一个boolean数组对应位置标记一下，递归结束后再还原。因为List频繁查找插入删除效率一般比较低，所以我们一般使用一个boolean数组去标记该位置元素是否被使用。
具体实现的代码为：
List<List<Integer>> list; public List<List<Integer>> permuteUnique(int[] nums) { list=new ArrayList<List<Integer>>();//最终的结果 List<Integer> team=new ArrayList<Integer>();//回溯过程收集元素 boolean jud[]=new boolean[nums.length];//用来标记 dfs(jud, nums, team, 0); return list; } private void dfs(boolean[] jud, int[] nums, List<Integer> team, int index) { int len = nums.length; if (index == len)// 停止 { list.add(new ArrayList<Integer>(team)); } else for (int i = 0; i < len; i++) { if (jud[i]) //当前数字被用过 当前即不可用 continue; team.add(nums[i]); jud[i]=true;//标记该元素被使用 dfs(jud, nums, team, index + 1); jud[i] = false;// 还原 team.remove(index);//将结果移除临时集合 } }
修改一下输出的结果和上面思维导图也是一致的：
邻里互换法实现无重复全排列
回溯的测试是试探性填充，是对每个位置进行单独考虑赋值。而邻里互换的方法虽然是也是递归实现的，但是他是一种基于交换的策略和思路。而理解起来也是非常简单，邻里互换的思路是从左向右进行考虑。
因为序列是没有重复的，我们开始将数组分成两个部分：暂时确定部分和未确定部分。开始的时候均是未确定部分，我们需要妥善处理的就是未确定部分。在未确定部分的序列中，我们需要让后面未确定的每一位都有机会处在未确定的首位，所以未确定部分的第一个元素就要和每一个依次进行交换(包括自己)，交换完成之后再向下进行递归求解其他的可能性，求解完毕之后要交换回来(还原)再和后面的进行交换。这样当递归进行到最后一层的时候就将数组的值添加到结果集中。如果不理解可以参考下图进行理解：
实现代码为：
class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>>list=new ArrayList<List<Integer>>(); arrange(nums,0,nums.length-1,list); return list; } private void arrange(int[] nums, int start, int end, List<List<Integer>> list) { if(start==end)//到最后一个 添加到结果中 { List<Integer>list2=new ArrayList<Integer>(); for(int a:nums) { list2.add(a); } list.add(list2); } for(int i=start;i<=end;i++)//未确定部分开始交换 { swap(nums,i,start); arrange(nums, start+1, end, list); swap(nums, i, start);//还原 } } private void swap(int[] nums, int i, int j) { int team=nums[i]; nums[i]=nums[j]; nums[j]=team; } }
那么邻里互换和回溯求解的全排列有什么区别呢?首先回溯法求得的全排列如果这个序列有序得到的结果是字典序的，因为其策略是填充，先小后大有序，而邻里互换没有这个特征。其次邻里互换在这种情况下的效率要高于回溯算法的，虽然量级差不多但是回溯算法需要维护一个集合频繁增删等占用一定的资源。
有重复序列的全排列
有重复对应的是力扣第47题 ，题目描述为：
给定一个可包含重复数字的序列
nums，按任意顺序 返回所有不重复的全排列。
示例 1：
输入：nums = [1,1,2] 输出： [[1,1,2], [1,2,1], [2,1,1]]
示例 2：
输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
提示：
1 <= nums.length <= 8
-10 <= nums[i] <= 10
这个和上面不重复的全排列略有不同，这个输入数组中可能包含重复的序列，我们怎么样采取合适的策略去重复才是至关重要的。我们同样针对回溯和邻里互换两种方法进行分析。
回溯剪枝法
因为回溯完整的比直接递归慢，所以刚开始并没有考虑使用回溯算法，但是这里用回溯剪枝相比递归邻里互换方法更好一些，对于不使用哈希去重的方法，首先进行排序预处理是没有悬念的，而回溯法去重的关键就是避免相同的数字因为相对次序问题造成重复，所以在这里相同数字在使用上相对位置必须不变，而具体剪枝条的规则如下：
- 先对序列进行排序
- 试探性将数据放到当前位置
- 如果当前位置数字已经被使用，那么不可使用
- 如果当前数字和前一个相等但是前一个没有被使用，那么当前不能使用，需要使用前一个数字。
思路很简单，实现起来也很简单：
List<List<Integer>> list; public List<List<Integer>> permuteUnique(int[] nums) { list=new ArrayList<List<Integer>>(); List<Integer> team=new ArrayList<Integer>(); boolean jud[]=new boolean[nums.length]; Arrays.sort(nums); dfs(jud, nums, team, 0); return list; } private void dfs(boolean[] jud, int[] nums, List<Integer> team, int index) { // TODO Auto-generated method stub int len = nums.length; if (index == len)// 停止 { list.add(new ArrayList<Integer>(team)); } else for (int i = 0; i < len; i++) { if (jud[i]||(i>0&&nums[i]==nums[i-1]&&!jud[i-1])) //当前数字被用过 或者前一个相等的还没用，当前即不可用 continue; team.add(nums[i]); jud[i]=true; dfs(jud, nums, team, index + 1); jud[i] = false;// 还原 team.remove(index); } }
邻里互换法
我们在执行递归全排列的时候，主要考的是要把重复的情况搞下去，邻里互换又要怎么去重呢？
使用HashSet这种方式这里就不讨论啦，我们在进行交换swap的时候从前往后，前面的确定之后就不会在动，所以我们要慎重考虑和谁交换。比如1 1 2 3第一个数有三种情况而不是四种情况(两个1 1 2 3为一个结果)：
1 1 2 3 // 0 0位置交换
2 1 1 3 // 0 2位置交换
3 1 2 1 // 0 3位置交换
另外比如3 1 1序列,3和自己交换，和后面两个1只能和其中一个进行交换，我们这里可以约定和第一个出现的进行交换，我们看一个图解部分过程：
所以，当我们从一个index开始的时候要记住以下的规则：同一个数只交换一次(包括值等于自己的数)。在判断后面值是否出现的时候，你可以遍历，也可以使用hashSet().当然这种方法的痛点就是判断后面出现的数字效率较低。所以在可能重复的情况这种方法效率一般般。
具体实现的代码为：
public List<List<Integer>> permuteUnique(int[] nums) { List<List<Integer>> list=new ArrayList<List<Integer>>(); arrange(nums, 0, nums.length-1, list); return list; } private void arrange(int[] nums, int start, int end, List<List<Integer>> list) { if(start==end) { List<Integer>list2=new ArrayList<Integer>(); for(int a:nums) { list2.add(a); } list.add(list2); } Set<Integer>set=new HashSet<Integer>(); for(int i=start;i<=end;i++) { if(set.contains(nums[i])) continue;上一篇： python实战】top1 数字组合 - 有四个数字：1、2、3、4，可以组成多少个互不相同且没有重复数字的三位数？各是多少？
下一篇： C++ 快速幂和大数模算法示例
推荐阅读