47. Permutations II
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] ]
難度:medium
題目:給定一組可能包含重複數的集合,返回所有可能的排列。
思路:先對陣列進行排序,為去重做準備。然後藉助遞迴遍歷所有數。重點在於,當每次選定一個數做完交換之後,恢復時要對兩個交換數及之間的所有數做排序。繼續為接下來的去重做準備。
class Solution { public List<List<Integer>> permuteUnique(int[] nums) { Arrays.sort(nums); List<List<Integer>> result = new ArrayList<>(); permuteUnique(nums, 0, new Stack<Integer>(), result); return result; } private void permuteUnique(int[] nums, int idx, Stack<Integer> stack, List<List<Integer>> result) { if (idx == nums.length) { result.add(new ArrayList<>(stack)); return; } for (int i = idx; i < nums.length; i++) { if (idx == i || nums[i] != nums[i - 1]) { stack.push(nums[i]); swap(nums, idx, i); permuteUnique(nums, idx + 1, stack, result); swap(nums, i, idx); Arrays.sort(nums, idx, i + 1); stack.pop(); } } } private void swap(int[] nums, int i, int j) { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; } }