Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Example:
Input: [1,1,2] Output: [ [1,1,2], [1,2,1], [2,1,1] ]
全排列II。一刷的时候直接抄答案，但是依然记不住，二刷终于搞懂了，来写个题解。这个题跟版本一相比只是多了一个条件，就是input数组里面是有重复元素的，但是得出的permutation里面不能有重复。
思路依然是backtracking，同时因为需要去掉重复元素带来的困扰，我们需要用一个visited数组来记录数字是否被用过。这里我参考了LC中文网一个大神的解释，讲的非常好，尤其帮助我理解了回溯的具体过程和怎么去重的部分。回溯的helper函数的主要部分还是跟其他回溯类型的题差不多，但是这个题需要先对input排序（帮助剪枝）和额外的visited数组记录。
时间O(N * N!)
空间O(N * N!)
Java实现
18行判断是否跳过当前数字，是如下两个原则
1 class Solution { 2 public List<List<Integer>> permuteUnique(int[] nums) { 3 List<List<Integer>> res = new ArrayList<>(); 4 if (nums == null || nums.length == 0) { 5 return res; 6 } 7 Arrays.sort(nums); 8 helper(res, new ArrayList<>(), nums, new boolean[nums.length]); 9 return res; 10 } 11 12 private void helper(List<List<Integer>> res, List<Integer> list, int[] nums, boolean[] visited) { 13 if (list.size() == nums.length) { 14 res.add(new ArrayList<>(list)); 15 return; 16 } 17 for (int i = 0; i < nums.length; i++) { 18 if (visited[i] || i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) { 19 continue; 20 } 21 visited[i] = true; 22 list.add(nums[i]); 23 helper(res, list, nums, visited); 24 visited[i] = false; 25 list.remove(list.size() - 1); 26 } 27 } 28 }
[LeetCode] 47. Permutations II
原文：https://www.cnblogs.com/cnoodle/p/13019326.html