47. 全排列 II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutations-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

import java.util.ArrayList;
import java.util.List;

class Solution {

    private static void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }

    private static void reverse(int[] nums, int start, int end) {
        while (start < end) {
            swap(nums, start++, end--);
        }
    }

    private static void next(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.length - 1;
            while (nums[i] >= nums[j]) {
                j--;
            }
            swap(nums, i, j);
        }
        reverse(nums, i + 1, nums.length - 1);
    }

    private static boolean isEqual(int[] original, int[] nums) {
        for (int i = 0; i < nums.length; ++i) {
            if (original[i] != nums[i]) {
                return false;
            }
        }
        return true;
    }

    private static List toList(int[] nums) {
        List item = new ArrayList<>(nums.length);
        for (int j = 0; j < nums.length; ++j) {
            item.add(nums[j]);
        }
        return item;
    }

    public static List> permuteUnique(int[] nums) {

        List> ret = new ArrayList<>();

        int[] original = new int[nums.length];
        System.arraycopy(nums, 0, original, 0, nums.length);

        do {
            ret.add(toList(nums));
            next(nums);
        } while (!isEqual(original, nums));

        return ret;
    }
}