可以发现和上一题不一样的地方，就是使用了一个boolean[] visited数组去记录哪些元素被访问哪些没有被访问，而不是通过contains方法去判断。另外就是使用了Set去存储排列结果，这样就能去掉重复结果，但效率不太行。
可以发现用Set去重效率十分的低。需要考虑在回溯过程中进行剪枝，去掉一些无效的中间状态。可以参考题解：https://leetcode-cn.com/problems/permutations-ii/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liwe-2/。图文并茂，这里直接上代码
class Solution { Set<List<Integer>> temp = new HashSet<>(); public List<List<Integer>> permuteUnique(int[] nums) { LinkedList<Integer> list = new LinkedList<>(); // 记录已经访问过的元素 boolean[] visited = new boolean[nums.length]; // 排序，方便剪枝 Arrays.sort(nums); backTrace(nums, list, visited); List<List<Integer>> res = new LinkedList<>(temp); return res; } private void backTrace(int[] nums, LinkedList<Integer> list, boolean[] visited) { if (list.size() == nums.length) { temp.add(new LinkedList(list)); return; } for (int i = 0; i < nums.length; i++) { if (visited[i]) { continue; } // 剪枝 if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) { continue; } // 下标为i的元素已经访问过 visited[i] = true; list.add(nums[i]); backTrace(nums, list, visited); // 移除list的元素同时将下标为i的元素置为未访问状态 list.removeLast(); visited[i] = false; } } }
可以发现时间从90ms -> 4ms，但这个击败率。。。
接下来看看重复字符串的， 剑指 Offer 38. 字符串的排列
其实这道和重复数字的大差不差，只是数据类型不一样罢了。。不信看代码
class Solution { public String[] permutation(String s) { // Set去重 Set<String> 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 + ","); }); return sb.substring(0, sb.length() - 1).toString().split(","); } private void backTrace(int index, char[] chs, Set<String> set, boolean[] visited, char[] con) { if (index == chs.length) { set.add(new String(con)); return; } for (int i = 0; i < chs.length; i++) { if (!visited[i]) { visited[i] = true; con[index] = chs[i]; backTrace(index + 1, chs, set, visited, con); visited[i] = false; } } } } 4、总结全排列问题，其实只要记住了这个思路和套路，基本上要写出来都没问题，万变不离其宗，多刷几道题就可以了。