46.全排列

题目描述：

给定一个没有重复的数组，返回其所有可能的全排列。

解题思路：

穷举的题目，用回溯法。

代码：

public List<List<Integer>> permute(int[] nums){ List<List<Integer>> result = new LinkedList<>(); ArrayList<Integer> numsArray = new ArrayList<>(); for(int num: nums) numsArray.add(num); traceback(numsArray, result, 0); return result; } public void traceback(ArrayList<Integer> nums, List<List<Integer>> result, int first){ //如果走到了最后，则加入结果数组中 if(first == nums.size()-1) result.add(new ArrayList<>(nums)); for(int i=first; i<nums.size(); i++){ //交换nums[first]和nums[i]的值，形成新的排列 Collections.swap(nums, first, i); //递归 traceback(nums, result, first+1); //再次交换nums[first]和nums[i]的值，还原 Collections.swap(nums, first, i); } }

代码理解：

算法的基本思想如下图，代码的走向是从上到下从左到右，其实就是用交换的方式遍历所有可能的排列。

47. 全排列2

题目描述：

给定一个可包含重复数字的序列，返回所有不重复的全排列。

解题思路：

其实这是全排列1的一般情况，首先来看一下全排列1的另一种解题思想：

public List<List<Integer>> permute(int[] nums) { List<List<Integer>> res = new ArrayList<>(); int[] visited = new int[nums.length]; backtrack(res, nums, new ArrayList<Integer>(), visited); return res; } private void backtrack(List<List<Integer>> res, int[] nums, ArrayList<Integer> tmp, int[] visited) { if (tmp.size() == nums.length) { res.add(new ArrayList<>(tmp)); return; } for (int i = 0; i < nums.length; i++) { if (visited[i] == 1) continue; visited[i] = 1; tmp.add(nums[i]); backtrack(res, nums, tmp, visited); visited[i] = 0; tmp.remove(tmp.size() - 1); } }

这个算法有点难理解，它用一个visited数组记录该次遍历已访问过的位置

第一轮一路走到n，将该数组存入结果集；第二轮，remove掉了最后两位，最后两位都是unvisited，但是回溯回来在tmp[nums.length-2]处 i 已经走到了nums[nums.length-1]位，因此数字n被填入temp[nums.length-2]处，数字n-1被填入temp[nums.length-1]处。（有博客说在回溯到tmp[nums.length-2]时只有最后一位是unvisited，是不对的，是因为游标 i 此时已经跳过了第n-1位，所以才将数字n填入n-1位，开单步调试看看变量怎么变得就知道了）

这是没有重复的情况，当有重复数字时，标红的那一行就需要换成如下语句，并且需要先对nums数组进行排序。

if(visited[i] == 1 || (i>0 && nums[i]==nums[i-1] && visited[i-1]==0)) continue;

 另一个判断条件是，如果nums[i]在nums数组中有排在其前面并且值相等的数，并且在这轮遍历中前面的相同数值的nums[i-1]还没有插入tmp结果集，那么就跳过nums[i]，因为如果将nums[i]插入，那么结果会和将nums[i-1]插入时的结果一样，就会造成重复。

 

转载于:https://www.cnblogs.com/yingying7/p/11129257.html