【题目】

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

【解析】

题意：求一个数组的全排列。与【LeetCode】Permutations 解题报告 不同的是，数组中的数有反复。

对于全排列，如今比較经常使用的算法就是依据 【LeetCode】Next Permutation 解题报告 从小到大逐个找出全部的排列。

算法：回溯、字典序法。

public class Solution {

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

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

        Arrays.sort(num);

        //首先得把原始数组加入到结果集

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

        for (int x : num) {

            list.add(x);

        }

        ans.add(list);

        //逐个加入下一个解

        for (int i = 1; i < factorial(num.length); i++) {

            nextPermutation(num);

        }

        return ans;

    }

    public void nextPermutation(int[] num) {

        //找到最后一个正序

        int i = num.length - 1;

        while (i > 0 && num[i] <= num[i - 1]) {

            i--;

        }

        if (i <= 0) return;

        //找到最后一个比num[i-1]大的数

        int j = num.length - 1;

        while (j >= i && num[j] <= num[i - 1]) {

            j--;

        }

        //交换

        int tmp = num[i - 1];

        num[i - 1] = num[j];

        num[j] = tmp;

        //逆排i-1之后的数

        int l = i, r = num.length - 1;

        while (l < r) {

            tmp = num[l];

            num[l] = num[r];

            num[r] = tmp;

            l++;

            r--;

        }

        //加入到结果集

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

        for (int x : num) {

            list.add(x);

        }

        ans.add(list);

    }

    public int factorial(int n) {

        return n == 0 ?

1 : n * factorial(n - 1);

    }

}

相关题目：【LeetCode】Permutations 解题报告 和 【LeetCode】Next Permutation
解题报告