Permutations II

Source

• leetcode: 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,1,2], [1,2,1], and
[2,1,1].

Java

public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        boolean[] used = new boolean[nums.length];
        Arrays.sort(nums);
        dfs(nums, new ArrayList<Integer>(), result, used);
        return result;
    }


    public void dfs(int[] nums, List<Integer> path, List<List<Integer>> result, boolean[] used){
        if(path.size()==nums.length){
            List<Integer> p = new ArrayList<Integer>(path);
            result.add(p);
            return;
        }
        for(int i=0; i<nums.length; i++){
            if(i>0 && nums[i]==nums[i-1] && !used[i-1]) continue;
            /*
            上面的判断其实并不影响最终结果，目的是为了让dfs能更快
            上面这一连串判断条件，重点在于要能理解!visited.contains(i-1)
            要理解这个，首先要明白i作为数组内序号，i是唯一的
            给出一个排好序的数组，[1,2,2]
            第一层递归            第二层递归            第三层递归
            [1]                    [1,2]                [1,2,2]
            序号:[0]                 [0,1]            [0,1,2]
            这种都是OK的，但当第二层递归i扫到的是第二个"2"，情况就不一样了
            [1]                    [1,2]                [1,2,2]            
            序号:[0]                [0,2]                [0,2,1]
            所以这边判断的时候!visited.contains(0)就变成了true，不会再继续递归下去，跳出循环
            步主要就是为了去除连续重复存在的，很神奇反正 = =||
            */
            if(!used[i]){
                used[i]=true;
                path.add(nums[i]);
                dfs(nums, path, result, used);
                path.remove(path.size()-1);
                used[i]=false;
            }
        }
    }
}