转载请联系bigsai公众号。前言大家好，好久不见！在写题和面试的过程中，我们经常会遇到一些排列组合题，全排列组合子集等问题非常经典。本文将带你吃透全编！找到完整的安排？完整的排列是：n个元素取n个元素（所有元素）和所有排列组合。寻求组合？组合是：n个元素取m个元素的所有组合（非排列）。子集？子集是：n个元素的所有子集（所有可能的组合）。一般情况下，全排列的值个数就是所有元素，不同的是排列顺序；组合就是选择固定数量的组合（不要看排列）；子集是扩展组合，所有可能的组合（同不同的Considerpermutations）。当然，这三种问题有相似之处，也略有不同。我们可能会接触到更多的全排列，因此您可以将组合和子集问题视为全排列的扩展变形。并且问题可能是是否有重复的字符需要处理。采用不同的策略去重也是非常关键和重要的！解决每个问题可能有很多方法。全排列中最受欢迎的是邻域交换法和回溯法，其他组合和子集问题都是经典回溯问题。本篇最重要最基础的就是掌握这两种方法实现的非重复全排列，其他的都是在此基础上进行改造扩展。全排列问题全排列，元素总数最多，区别在于排列顺序。不重复序列的全排列题恰好是里口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进行标记，继续向下递归。当所有元素都标记完毕后，依次收集标记的元素存入结果，当前层递归结束，返回上一层（同时清除当前层的标记元素）。这一直持续到最后。如果回溯的过程从伪代码过程看大致如下：递归函数：如果集合中的所有元素都被标记：对结果集添加暂存否则：选择集合中一个未标记的元素存入临时集合。标记要标记的元素使用下一层递归函数（本层递归结束）标记该元素没有被使用很多，需要一个List来存放临时结果，但是我们有两种方式处理原始集合。第一种是用List来存储集合，用完后取出再递归到下一层，递归完成再添加到原来的位置。另一种思路是用一个固定的数组来存储，用一个布尔数组来标记所使用的对应位置的对应位置，递归结束后再恢复。因为List频繁的查找、插入、删除，效率普遍较低，所以我们一般用一个boolean数组来标记这个位置的元素是否被使用。具体实现代码为：List>list；publicList>permuteUnique(int[]nums){list=newArrayList>();//最终结果Listteam=newArrayList();//元素集合booleanjud[]=newboolean[nums.length];//用于标记dfs(jud,nums,team,0);returnlist;}privatevoiddfs(boolean[]jud,int[]nums,Listteam,intindex){intlen=nums.length;if(index==len)//stop{list.add(newArrayList(team));}elsefor(inti=0;i>permute(int[]nums){List>list=newArrayList>();排列(nums,0,nums.length-1,list);returnlist;}privatevoidarrange(int[]nums,intstart,intend,List>list){if(start==end)//将最后一个加到结果中{Listlist2=newArrayList();for(inta:nums){list2.add(a);}list.add(list2);}for(inti=start;i<=end;i++)//未定部分开始交换{swap(nums,i,start);arrange(nums,start+1,end,list);swap(nums,i,start);//恢复}}privatevoidswap(int[]nums,inti,intj){inteam=nums[i];nums[i]=nums[j];nums[j]=team;}}那么neighborhoodswap和backtrackingsolutionfullpermutation有什么区别呢？首先，如果回溯法得到的全排列是有序的，结果是字典序，因为策略是填充，先小后大的顺序，neighborswap没有这个特性。其次，这种情况下邻居交换的效率要高于回溯算法。虽然数量级差不多，但是回溯算法需要维护一个集合，频繁的增删改查等需要占用一定的资源。具有重复序列和重复的完整排列对应于Likou的第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]]Tips:1<=nums.length<=8-10<=nums[i]<=10这个和上面的非重复全排列略有不同，这个输入数组可能包含重复序列，如何我们采用适当的策略来重复是至关重要的。我们还分析了回溯和邻域交换方法。回溯剪枝法比直接递归慢，因为回溯是完全的，所以一开始没有考虑回溯算法，但是这里用回溯剪枝比递归邻域交换法要好。对于不使用hash去重的方法，首先排序预处理没有悬念，而回溯法去重的关键是避免相同数字因为相对顺序问题出现重复，所以相对位置这里使用的相同数字必须保持不变，具体剪枝规则如下：先对序列进行排序，暂定数据放在当前位置。如果当前位置的号码已经被使用，则不能再使用。如果当前数与上一个数相等，但上一个数没有被使用过，则当前不能使用，需要使用上一个数。回溯选择策略的思路很简单，实现也很简单：List>list;publicList>permuteUnique(int[]nums){list=newArrayList>();Listteam=newArrayList();booleanjud[]=newboolean[nums.length];Arrays.sort(nums);dfs(jud,nums,team,0);returnlist;}privatevoiddfs(boolean[]jud,int[]nums,Listteam,intindex){//TODOAuto-generatedmethodstubintlen=nums.length;if(index==len)//stop{list.add(newArrayList(team));}elsefor(inti=0;i0&&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);}}邻域交换方法我们在进行递归全排列的时候，主要考的是去掉重复的情况，如何去掉neighborswap的重复呢？HashSet的使用方法这里不再赘述。当我们交换swap时，我们会从前到后。经过之前的确认，我们不会再动了，所以我们要慎重考虑和谁交换。比如第一个数1123有三种情况而不是四种情况（两个1123是一个结果）：1123//00位置交换2113//02位置交换3121//03位置交换其他如311序列，3和自己交换，后两个1只能和其中一个交换。我们可以同意与出现在这里的第一个交换。让我们看一下过程的图形部分：邻里交换是一个过程。因此，当我们从一个索引开始时，一定要记住以下规则：同一个数只交换一次（包括其值等于自身的数）。在判断是否出现以下值时，可以遍历或者使用hashSet()。当然，这种方法的痛点在于对后面出现的数字的判断效率低下。因此，该方法在可能重复的情况下效率一般。具体实现代码为：publicList>permuteUnique(int[]nums){List>list=newArrayList>();arrange(nums,0,nums.length-1,list);returnlist;}privatevoidarrange(int[]nums,intstart,intend,List>list){if(start==end){Listlist2=newArrayList();for(inta:nums){list2.add(a);}list.add(list2);}Setset=newHashSet();for(inti=start;i<=end;i++){if(set.contains(nums[i]))continue;set.add(nums[i]);swap(nums,i,start);arrange(nums,start+1,end,list);swap(nums,i,start);}}privatevoidswap(int[]nums,inti,intj){inteam=nums[i];nums[i]=nums[j];nums[j]=team;}组合题组合题可以考虑是全排列的变体，问题描述（扣77题）：给定两个整数n和k，返回1...n中k个数的所有可能组合。示例：输入：n=4,k=2输出：[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],]分析：这道题是经典的回溯问题。组合需要记住只看元素而不看元素顺序，比如ab和ba是同一个组合。避免这样的重复是核心，要避免这样的重复，就要用一个int类型来保存当前选中元素的位置。下次只能遍历选中下标位置之后的数字，通过一个数字类型得到k个数字，由处理回当前层的数字个数控制。完全排列和组合之间的一些差异也很容易实现。需要创建一个数组来存放对应的编号，使用boolean数组判断是否使用了对应的位置编号。这里，不需要在List中存储数字，最后通过判断boolean数组给结果加上值也是可行的。实现代码为：classSolution{publicList>combine(intn,intk){List>valueList=newArrayList>();//resultintnum[]=newint[n];//数组存储1-nbooleanjud[]=newboolean[n];//用于判断是否使用for(inti=0;iteam=newArrayList();dfs(num,-1,k,valueList,jud,n);returnvalueList;}privatevoiddfs(int[]num,intindex,intcount,List>valueList,booleanjud[],intn){if(count==0)//k个元素满了{Listlist=newArrayList();for(inti=0;i>subsets(int[]nums){List>valueList=newArrayList>();booleanjud[]=newboolean[nums.length];Listteam=newArrayList();dfs(nums,-1,valueList,jud);returnvalueList;}privatevoiddfs(int[]num,intindex,List>valueList,booleanjud[]){{//每一个递归函数都要在结果中加上Listlist=newArrayList();for(inti=0;i>subsetsWithDup(int[]nums){Arrays.sort(nums);booleanjud[]=newboolean[nums.length];列表<列表<整数>>valueList=newArrayList<列表<整数>>();dfs(nums,-1,valueList,jud);returnvalueList;}privatevoiddfs(int[]nums,intindex,List>valueList,boolean[]jud){//TODOAuto-generatedmethodstubListlist=newArrayList<整数>();for(inti=0;i0&&jud[i-1]&&nums[i]==nums[i-1])){jud[i]=true;dfs(nums,i,valueList,jud);jud[i]=false;}}}}Conclusion到这里，把本文的全排列、组合、子集问题介绍到这里，特别是问题处理的思路和策略，重复数据删除。当然类似这样的题还有很多，多刷几下就能很好的掌握，敬请期待！
