Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,

[1,1,2] have the following unique permutations:

  1. [
  2.   [1,1,2],
  3.   [1,2,1],
  4.   [2,1,1]
  5. ]

Solution:

  1. public class Solution {
  2.   public List<List<Integer>> permuteUnique(int[] nums) {
  3.     Arrays.sort(nums);
  4.     List<List<Integer>> res = new ArrayList<List<Integer>>();
  5.     boolean[] used = new boolean[nums.length];
  6.     helper(nums, used, new ArrayList<Integer>(), res);
  7.     return res;
  8.   }
  10.   private void helper(int[] nums, boolean[] used, List<Integer> sol, List<List<Integer>> res) {
  11.     if (sol.size() == nums.length) {
  12.       res.add(new ArrayList<Integer>(sol));
  13.       return;
  14.     }
  16.     for (int i = 0; i < nums.length; i++) {
  17.       // avoid duplication
  18.       if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
  19.         continue;
  20.       }
  22.       if (!used[i]) {
  23.         used[i] = true;
  24.         sol.add(nums[i]);
  25.         helper(nums, used, sol, res);
  26.         sol.remove(sol.size() - 1);
  27.         used[i] = false;
  28.       }
  29.     }
  30.   }
  31. }