回溯---全排列 Posted on 2021-07-28 00:00:00 2021-07-29 00:00:00 by Author 摘要 给定一个不含重复数字的数组 nums ，你能得到该集合所有可能的全排列吗？？？ # 回溯---全排列 1. 题目描述 - 给定一个不含重复数字的数组 `nums` ，返回其 **所有可能的全排列** 。你可以 **按任意顺序** 返回答案。 - **提示：** - `1 <= nums.length <= 6` - `-10 <= nums[i] <= 10` - `nums` 中的所有整数 **互不相同** 2. 示例描述 - 示例一 ``` 输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] ``` - 示例二 ``` 输入：nums = [0,1] 输出：[[0,1],[1,0]] ``` 3. 解题思路 - 高中的时候学过集合，经常会遇到对n个数字进行全排列的问题，求出n个数全排列的集合。一般遇到这个问题只要不粗心大意都能完成。那么这道题交给计算机去完成，应该怎么实现尼。 - 其实解决这个问题，安装我们以前做题的思路用计算机语言表示出来就可以了。那怎么实现尼，一起看看吧。首先举个栗子，给定集合为[1,2,3]。怎么求这个集合的全排列尼，第一步也就是第一层我们从[1,2,3]中选取一个数，这里有三种选法，可以选1，可以选2，可以选3，这里我们先选1，接下来第二层我们从集合[2,3]选取一个数，这一层可以选2，也可以选3，第二层先选2，最后从第三层中集合只剩[3]，我们选择3，此时这一层集合遍历完毕，选出来的结果为[1,2,3]。第三层已经遍历完成，此时我们在回到第二层，第二层在上次中我们选择了2，这次我们选择3，此时在到达第三层，只剩下集合{2}，第三层我们只能选择2，第三层遍历完成，此时结果为[1,3,2]。那么这次的第三层也遍历完成，返回第二层，同时第二层也遍历完成，这次我们返回第一层，由于第一层第一次选择的是1，那么我们这次可以选择2，其余集合为[1,3]，继续按照之前的步骤，等到第一层遍历完成后，这个集合也就遍历完成。那么最终结果集也就找到了。 - 上面讲解的是怎么一步一步解决这道题目的，同时上面的步骤大家会发现有递归与回溯的思想在里面。那么这里还是用我自己总结的递归回溯五步法进行解决。首先`第一步`递归的出口条件就是每一个子集的集合长度与原集合长度相等的时候说明本次排列完成，加入最终结果集中。`第二步`就是循环遍历集合了。这里有一个非常值得思考的问题就是，每次递归的时候，循环遍历集合是遍历集合中的某一部分，还是遍历整个集合。其实是遍历集合的某一部分，为什么尼，因为在本次递归的时候，之前层已经使用的元素不能再使用了，所以本层集合是整个集合的某一部分。本人下面的代码在处理这个问题的时候，每次递归遍历集合的时候是遍历整个集合，然后再循环遍历中再处理之前已经使用的元素，从而达到在本层遍历时，只使用集合的一部分元素。`第三步`就是记录本层遍历的值，把本层遍历的值加入临时结果集中。`第四步`就是继续向下层递归以达到可以完整的遍历整个集合。`第五步`就是回溯了，因为在没到达一层的时候，我们在处理本层集合中的每个元素时，要保证处理每个元素的初始状态都要一样，所以这里回溯，就能保证在该层，处理每个元素时的初始状态保持一样，从而达到筛选的过程，也保证顺利的完成这个递归的过程。 - 以上是我个人自己的理解，下面是具体实现。 4. 代码示例 ```java //最终结果集 List<List<Integer>> result = new ArrayList<>(); public List<List<Integer>> permute(int[] nums) { //调用自己写的全排列递归回溯方法，找到所有的全排列 prem(nums, new LinkedList<>()); //返回最终结果 return result; } public void prem(int[] nums, LinkedList<Integer> re) { //如果临时结果集长度与集合长度一样，说明本次排列完成 if (re.size() == nums.length) { //本次排列结果加入最终结果集合 result.add(new ArrayList<>(re)); } //每次调用递归的时候都遍历整个集合 //按理说应该遍历集合中的某一部分 //我这里没有进行处理，在循环中做了一步筛选过程，也能达到遍历集合某一部元素的效果 for (int i = 0; i < nums.length; i++) { //这里就是筛选过程 //临时集合中，如果之前访问过该元素，那么本次就不能使用该元素，继续处理本层下一个元素 if (re.contains(nums[i])) continue; //否则记录本层用的元素 re.add(nums[i]); //继续递归下一层 prem(nums, re); //这里回溯的思想，就是回溯到本层的时候，保证本层遍历时初始状态都一样 //也就保证选取本层集合中的元素都是平等对待的 re.removeLast(); } } ```
{{ item.content }}
{{ child.content }}