Description

Given a list of numbers with duplicate number in it. Find all unique permutations.

Example

For numbers[1,2,2]the unique permutations are:

[
  [1,2,2],
  [2,1,2],
  [2,2,1]
]

Solution

如何避免重复的permutation？
以[1, 2, 2]为例，在添加了1的情况下，再添加第二个数的时候只处理第一个2，忽略第二个2. 因此，遇到相同的数，在同一个位置上，总是只处理相同数中第一个出现的数。
怎样保证再同一个位置只处理相同数中的第一个数呢？用一个boolean的数组来记录每个nums中的数有没有被添加到结果list中。如果nums[i] == nums[i-1]说明第i个数是重复数字中不是第一个的数，此时如果boolean[i-1]==false说明第i-1个数没有被添加到当前的结果list中，也就是说在当前位置上，第i个数应该被忽略掉。

PermutationI中用list.contains[nums[i]]来判断要不要加nums[i]，这次就可以直接用visited[i]来判断了

class Solution {
    /**
     * @param nums: A list of integers.
     * @return: A list of unique permutations.
     */
    public List<List<Integer>> permuteUnique(int[] nums) {
        // Write your code here
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (nums == null) {
            return result;
        }

        Arrays.sort(nums);
        List<Integer> list = new ArrayList<Integer>();
        boolean[] visited = new boolean[nums.length];
        permuteUnique(nums, result, list, visited);
        return result;
    } 

    private void permuteUnique(int[] nums, List<List<Integer>> result, List<Integer> list, boolean[] visited) {
        if (list.size() == nums.length) {
            result.add(new ArrayList<Integer>(list));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (visited[i] || (i > 0 && nums[i] == nums[i-1] && !visited[i-1])) {
                continue;
            }

            list.add(nums[i]);
            visited[i] = true;
            permuteUnique(nums, result, list, visited);
            visited[i] = false;
            list.remove(list.size() - 1);
        }
    }
}