排列的消序法,排列组合消序法

　　1.了解所有的安排。追溯所有排列是指从N个元素中取出N个元素，按一定顺序排列。所有的安排都叫

全排列

　　n个元素分为n个元素中有重复元素的情况和n个元素中没有重复元素的情况。没有重复因素的好处是，重要的是有重复因素，这是我们在求解的过程中需要处理的。

　　追根溯源名字很大，但本质是

穷举

　　(A) 46。完整的安排

　　2) 47.完整序列II

　　3)剑指提供38。字符串排序。

　　2.完全序列问题的分析。例如，给定序列[1，2，3]，找出所有可能的完整序列。

　　试着在纸上写，[1，2，3]，[1，3，2]，[2，1，3]，[3，1，2]，[3，3，2，2]，[3，3，2，2]

　　尝试抽象到下面的树。

　　从根节点开始遍历，只需记录路径上的数字，就可以排序到叶节点，遍历树得到完整的排列。可以定义以下概念：

　　选定列表：已经选定的元素。可用列表：可选元素。

　　这里，直到叶节点，当可选列表实际为空时，此时获得数组。与二叉树扫描一样，当我们到达叶子的节点时，我们需要返回到那个节点，并转到那个兄弟节点。所以，我们得到完整的数组后，把选中列表的元素一个个弹出来，放到未选中列表中，然后重新选择。

　　那么，回溯法的伪代码可以总结如下

　　If(选择列表长度==元素列表长度)完全排列元素列表中的for元素，以确定是否在选择列表#中选择了某个元素。添加)元素)回溯)元素列表，选择列表)取消选择列表)移除)元素)3 .实例分析3.1我们先来看看不重叠元素46的完整排列。所有阵列

　　按照上面的思路，其实很快就要写了。

　　类解决方案{ listlistintergeres=new linked list(；publiclistlistintegerpermute(int[]nums))linkedlistintegertrack=新的链接列表；回溯(NUMS，跟踪)；返回结果；}如果} privatewidbacktrace(int[]nums，LinkedListInteger track )//相等，则完整数组If(track . size)==nums . length } for(inti=0；i nums.lengthI) (/如果这个元素已经存在，if(track . contains)nums[I]){ continue；//选择元素track . add(nums[I])；回溯(NUMS，跟踪)；select track . remove alst()；}}不是和模板差不多吗？

　　3.2包含重复元素的完整数组47。全阵II和剑指阵提供38。字符串。

　　一个是数字，一个是字符串。

　　请先看看数字。如果你有以上问题的基础，这个问题其实不难。求解过程中有两点需要注意。

　　用contains方法，我们无法判断列表中是否有重复的元素，所以无法得到数组。因为需要非重叠数组而不是非重叠元素，所以需要布尔数组来确定是否将元素添加到选定列表中。获得所有数组后，必须删除重复排序。在这里，您可以用集合替换数据结构并重新定位它，然后用列表替换集合。但是，这种方法效率非常低。因为有很多无效状态。最好的办法是在回溯中剪枝，在无效状态下直接跳过计算。

Set去重

　　类解决方案{ setlistingertemp=new hashset(；PublilistListIntegerPermuteUnique(int[]nums){链接列表集成器列表

　　=新链表()；//记录已经访问过的元素boolean[]visited=new boolean[num。长度]；回溯(nums，列表，已访问)；ListListInteger RES=新链表(temp)；返回RES } private void back trace(int[]nums，LinkedListInteger list，boolean[]visited){ if(list。size()==nums。长度){温度。add(新链表(list))；返回；} for(int I=0；I nums . length I){ if(visited[I]){ continue；} //下标为我的元素已经访问过visited[I]=true；列表。add(nums[I])；回溯(nums，列表，已访问)；//移除目录的元素同时将下标为我的元素置为未访问状态列表。移除last()；visited[I]=false；} }} 可以发现和上一题不一样的地方，就是使用了一个布尔[]已访问数组去记录哪些元素被访问哪些没有被访问，而不是通过包含方法去判断。另外就是使用了一组去存储排列结果，这样就能去掉重复结果，但效率不太行。

　　可以发现用一组去重效率十分的低。

需要考虑在回溯过程中进行剪枝，去掉一些无效的中间状态

　　class Solution { set list integer temp=new HashSet()；public list integer permute unique(int[]nums){链表integer list=new linked list()；//记录已经访问过的元素boolean[]visited=new boolean[num。长度]；//排序，方便剪枝数组。排序(nums)；回溯(nums，列表，已访问)；ListListInteger RES=新链表(temp)；返回RES } private void back trace(int[]nums，LinkedListInteger list，boolean[]visited){ if(list。size()==nums。长度){温度。add(新链表(list))；返回；} for(int I=0；I nums . length I){ if(visited[I]){ continue；} //剪枝if (i 0 nums[i]==nums[i - 1]！已访问[i - 1]) {继续；} //下标为我的元素已经访问过visited[I]=true；列表。add(nums[I])；回溯(nums，列表，已访问)；//移除目录的元素同时将下标为我的元素置为未访问状态列表。移除last()；visited[I]=false；} }}

　　可以发现时间从90毫秒-4毫秒，但这个击败率。

　　接下来看看重复字符串的，剑指出价38。字符串的排列

　　其实这道和重复数字的大差不差，只是数据类型不一样罢了。不信看代码

　　类解{ public String[]permutation(String s){//Set去重SetString set=new HashSet()；char[]CHS=s . tochararray()；//记录已经访问过的字符boolean[]visited=new boolean[s . length()]；char[]temp=new char[s . length()]；backTrace(0，chs，set，visited，temp)；StringBuilder sb=new StringBuilder()；set.stream().forEach(str - { sb.append(str ，)；});返回sb.substring(0，sb.length() - 1).toString().拆分(,);} private void backTrace(int index，char[] chs，SetString set，boolean[] visited，char[]con){ if(index==CHS。长度){ set。add(新字符串(con))；返回；} for(int I=0；我很高兴。长度；我){如果(!visited[I]){ visited[I]=true；con[index]=CHS[I]；回溯（索引1、chs、set、visited、con)；visited[I]=false；} } }} 4、总结全排列问题，其实只要记住了这个思路和套路，基本上要写出来都没问题，万变不离其宗，多刷几道题就可以了。