047 Permutations II 有重复数字的全排列

给定一个可能包含重复数字的集合，返回所有可能的不同全排列。
例如,
[1,1,2] 有以下不同全排列：
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

详见：https://leetcode.com/problems/permutations-ii/description/

Java实现：

class Solution {

    public List<List<Integer>> permuteUnique(int[] nums) {

        List<List<Integer>> res = new ArrayList<List<Integer>>();

        int size = nums.length;

        if(size==0||nums==null){

            return res;

        }

        boolean[] used = new boolean[size];

        List<Integer> out = new ArrayList<Integer>();

        Arrays.sort(nums);

        dfs(nums, used, out,res);

        return res;

    }

    public void dfs(int[] nums, boolean[] used, List<Integer> out,List<List<Integer>> res) {

        if(out.size()==nums.length) {

            res.add(new ArrayList<Integer>(out));

            return ;

        }

        for (int i=0; i<nums.length; i++) {

            // 当前位置的数已经在List中了

            if(used[i]){

                continue;

            }

            // 当前元素与其前一个元素值相同 且 前元素未被加到list中，跳过该元素

            if(i>0 && nums[i]==nums[i-1] && !used[i-1]){

                continue;

            }

            // 深度优先搜索遍历

            used[i]=true;

            out.add(nums[i]);

            dfs(nums, used, out, res);

            out.remove(out.size()-1);

            used[i]=false;

        }

    }

}

参考：https://blog.csdn.net/jacky_chenjp/article/details/66477538