33.算法学习之全排列‖

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

标签：回溯算法

示例：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

我的思路：这个题目和上一篇题目一样，都是全排列。不同的是，这个题目的输入参数数组中可以包含重复数字，而且输出结果是所有的不重复的全排列，可以参考一下例子。那么我们该怎么做呢？ 思考ing .... 这类的题目，输入参数里面有重复数字，我们最好还是将输入数组排序一下，将相同元素放在一起，这样我们进行回溯的时候就比较有序，假如不排序，那么回溯的时候取值就比较复杂，容易出错。我的代码如下：

public static List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        back(nums, new boolean[nums.length], new ArrayList<>(), res);
        return res;
    }

    public static void back(int[] nums, boolean[] used, List<Integer> pick, List<List<Integer>> res) {
        if (pick.size() == nums.length) {
            res.add(new ArrayList<>(pick));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i] || i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue;
            }
            pick.add(nums[i]);
            used[i] = true;
            back(nums, used, pick, res);
            used[i] = false;
            pick.remove(pick.size() - 1);
        }
    }

以上解答是学习上一篇回溯算法中的方法二，利用boolean[]数组，当然，输入数组得先进行排序，然后，在回溯的时候，每次取值判断如下

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

这个意思是 当前元素使用过就跳过。或者 当前元素与前一个元素相等，而且前一个元素没有被使用过就跳过， 因为我们排序后，相同的元素需要按照从前往后的顺序去取，若前一个元素还没被使用过，就证明当前步骤不合法，就跳过。

当前文章和上一篇文章是回溯算法里很经典的题目，求得输入参数的全排列。

以上就是我的解答了，如有错误，请各位大佬指出，谢谢！

若对您有帮助，大佬们帮我点个赞哈~~ : )