Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.
首先排序,对于有重复数据的数组,排序可以方便剪枝。
回溯,每次遍历数组内的元素。
创建一个数组记录元素是否已被遍历。
遍历时如果数组已经被记录,或者当前元素与数组中的上一个元素相等,且上一个数组未被选择,则跳过。
(如果上一个同样的数字没被选择,则放弃这个排列。即在元素相同时,优先选择前面的元素进行排列)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| class Solution { public List<List<Integer>> permuteUnique(int[] nums) { List<List<Integer>> ret = new ArrayList<>(); Arrays.sort(nums); int[] visited = new int[nums.length]; backtracking(ret, new ArrayList<>(), visited , nums); return ret; }
private void backtracking(List<List<Integer>> ret, List<Integer> arr, int[] visited, int[] nums){ if(arr.size() == nums.length){ ret.add(new LinkedList<>(arr)); return; } for(int i = 0; i < nums.length; i++){ if(visited[i] == 1) continue; if(i > 0 && nums[i] == nums[i-1] && visited[i-1] == 0) continue; arr.add(nums[i]); visited[i] = 1; backtracking(ret, arr, visited, nums); visited[i] = 0; arr.remove(arr.size()-1); } } }
|