【leetcode 47. 全排列 II 解析】

官方题解太难理解了，看看怎么修改下更方便理解呢。

先看一下原题：

47. 全排列 II

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

示例 1：

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

示例 2：

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

提示：

    1 <= nums.length <= 8
    -10 <= nums[i] <= 10

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

官方题解:

class Solution {
    boolean[] vis;
 
    public List<List<Integer>> permuteUnique(int[] nums) {
        // 结果集
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        // 处理过程中用到的子集容器
        List<Integer> perm = new ArrayList<Integer>();
        // 存放数的位置是否被访问
        vis = new boolean[nums.length];
        // 排序主要的目的是把一样的数放到一起
        Arrays.sort(nums);
        // 调用递归收集每一项子集
        backtrack(nums, ans, 0, perm);
        return ans;
    }
    // 递归函数
    public void backtrack(int[] nums, List<List<Integer>> ans, int idx, List<Integer> perm) {
        // 递归最重要的终止条件（写错都没事，但不能停不下来）
        if (idx == nums.length) {
            ans.add(new ArrayList<Integer>(perm));
            return;
        }
        // 开始套娃表演了...
        for (int i = 0; i < nums.length; ++i) {
            // 这边是全排列去重的关键，前面数都排好序了，只要判断同一个数在当前位置被访问过后面的数直接跳过；关键是 !vis[i - 1] 怎么理解啊？？ 
            if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
                continue;
            }
            perm.add(nums[i]);
            vis[i] = true;
            backtrack(nums, ans, idx + 1, perm);
            vis[i] = false;
            perm.remove(idx);
        }
    }
}
 
 
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/permutations-ii/solution/quan-pai-lie-ii-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

递归方法中 !vis[i - 1] 这行代码怎么理解？反正从逻辑角度挺难懂，但我们用缺失部分逻辑的方法反证他的意义就会清楚些。

改成这样: if (vis[i] || (i > 0 && nums[i] == nums[i - 1] )) continue;

用这样例测试：System.out.println(new Solution().permuteUnique(new int[]{1, 1, 2, 2}));

结果输出为空，因为位置1上选1，位置2上跳过第一个数判断第二个数也是1且和第一个数一样所以又跳过了，后面的2提前访问放在位置2上，导致后面两位置上一个数也选不了。

所以这个逻辑可以这样理解：当前数与前一数一样时，如果前一数在上一位置访问过了，那当前数也要选择一次（属于第一次），后面再有一样的数就可以跳过了。

下面是更容易理解的解法，也可以参考一下：

static class Solution02 {
        boolean[] visit;
        int[] nums;
        int size;
        List<List<Integer>> ans = new ArrayList<>();
        LinkedList<Integer> output = new LinkedList<>();
 
 
        /**
         * leetcode 47. 全排列
         *
         * @param nums
         * @return
         */
        public List<List<Integer>> permuteUnique(int[] nums) {
            Arrays.sort(nums);
            this.size = nums.length;
            visit = new boolean[size];
            this.nums = nums;
 
            recur(0);
            return ans;
        }
 
        public void recur(int p) {
            if (p >= size) {
                ans.add(new ArrayList<>(output));
                return;
            }
            Integer last = null;  // 存放当前位置，上一次访问过的数
            for (int i = 0; i < size; i++) { 
                // 当前位置 同一个数只能访问一次（这边是全排列去重的关键）
                if (visit[i] || (i > 0 && last != null && nums[i] == last)) continue;
                last = nums[i];
                output.add(last);
                visit[i] = true;
                recur(p + 1);
                visit[i] = false;
                output.remove(p);
            }
        }
    }