Permutations 16

Question

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] ]

Challenge

Using recursion to do it is acceptable. If you can do it without recursion, that would be great!

Solution

Recursion: 与Permutations 15类似，但是因为有重复元素，为了避免重复答案，有几点要注意。

1) 将所有重复元素排在一起，因此需要对输入数组先进行排序。

2) 用一个visit数组记录元素的状态，在list中为1，否则为0

3) 避免重复的方法：重复元素不能越过第一个元素取后面的重复元素，即若第一个重复元素不在list中，后面的重复元素不能加入list。因此在加入元素时，需要判断该元素值是否和前一个元素相等，同时前一个元素是否在list中。

Non-Recursion: 之后补上

代码如下：

class Solution {
    /**
     * @param nums: A list of integers.
     * @return: A list of unique permutations.
     */
    public ArrayList<ArrayList<Integer>> permuteUnique(ArrayList<Integer> nums) {
        // write your code here
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> list = new ArrayList<Integer>();

        if(nums == null || nums.size() == 0){
            return result;
        }
        //用一个visit数组来记录元素是否已经被加入list
        int[] visit = new int[nums.size()];
        //必须将相同元素放在一起，这样下面的判断重复的条件才能实现
        Collections.sort(nums);
        permuteHelper(result, list, nums, visit);
        return result;
    }

    public void permuteHelper(ArrayList<ArrayList<Integer>> result, ArrayList<Integer> list, ArrayList<Integer> nums, int[] visit){
        if(list.size()==nums.size()){
            result.add(new ArrayList<Integer>(list));
            return;
        }

        for(int i=0; i<nums.size(); i++){
            //若该元素未被加入list，同时前面相等值的元素也未被加入list，则该元素不能先被加入，否则会出现重复情况
            if(visit[i] == 1 || (i != 0 && nums.get(i) == nums.get(i-1) && visit[i - 1] == 0)){
                continue;
            }
            visit[i] = 1;
            list.add(nums.get(i));
            permuteHelper(result, list, nums, visit);
            list.remove(list.size()-1);
            visit[i] = 0;
        }
    }
}

Non-Recursion:

之后补上

Related Question

String Permutation II 10