Leetcode-047-全排列 II

题目描述

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

示例:

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

方法：回溯+剪枝

• 这一题是在「力扣」第 46 题： “全排列” 的基础上增加了“序列中的元素可重复”这一条件，但要求返回的结果又不能有重复元素。

• 思路：在一定会产生重复的地方进行剪枝

• 剪枝的方法
  • 一个比较容易想到的方法就是在结果集里面去重，但是问题来了，这里的结果集里面是一个列表，对列表的去重可没有HashSet那么容易
  • 如果要比较两个列表是否一样，一个很显然的办法就是排序，而且是一开始就进行排序，去除重复的选项。 一旦发现这一支搜索下去可能搜索到重复的元素就停止搜索，这样结果集中不会包含重复元素。

• 产生重复结点的地方，正是图中标注了“剪刀”，且被绿色框框住的地方。

• 大家也可以把第 2 个 1 加上 ' ，即 [1, 1', 2] 去想象这个搜索的过程。只要遇到起点一样，就有可能产生重复。

  • 这里有一个特别细节的地方
  • 在图中 ② 处，搜索的数也和上一次一样，但是上一次的 1 还在使用中；
  • 在图中 ① 处，搜索的数也和上一次一样，但是上一次的 1 刚刚被撤销，正是因为刚被撤销，下面的搜索中还会使用到，因此会产生重复，剪掉的就应该是这样的分支。

代码实现：在第 46 题的基础上，要加上这样一段代码：

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

// 思想：在一定会产生重复结果集的地方剪枝
// 一个比较容易想到的办法是在结果集中去重。
// 但是问题又来了，这些结果集的元素是一个又一个列表，对列表去重不像用哈希表对基本元素去重那样容易。

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        // 结果集
        List<List<Integer>> res = new ArrayList<>();

        // 特判
        if (nums.length == 0){
            return res;
        }

        // 在搜索之前就要对元素进行排序：排序是剪枝的前提
        // 一旦发现这一支搜索下去可能会遇到重复的元素就停止搜索
        Arrays.sort(nums);

        boolean[] used = new boolean[nums.length];

        // 全局唯一的辅助结果集
        ArrayList<Integer> temp = new ArrayList<>();
        backtrack(nums,0,used,temp,res);
        return res;
    }

    private void backtrack(int[] nums, int depth, boolean[] used, ArrayList<Integer> temp, List<List<Integer>> res) {
        // 递归结束的条件
        if (depth == nums.length){
            res.add(new ArrayList<>(temp));
            return;
        }

        // for循环进行操作
        for (int i = 0; i < nums.length; i++) {
            // 1. 如果当前数已经使用过
            if (used[i]) {
                continue;
            }

            // 1. 剪枝条件 ： i > 0 是为了保证 nums[i - 1] 有意义
            // 写！user[i] 是因为nums[i-1]在回溯的时候刚刚被撤销的选择的情况
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]){
                continue;
            }

            // 2. 做出选择
            temp.add(nums[i]);
            used[i] = true;

            // 3. backtrack
            backtrack(nums,depth + 1,used,temp,res);

            // 4. 撤销选择
            used[i] = false;
            temp.remove(temp.size() - 1);
        }
    }
}

复杂度分析：（理由同第 46 题，重复元素越多，剪枝越多。但是计算复杂度的时候需要考虑最差情况。）

• 时间复杂度： O(N*N!)
• 空间复杂度： O(N*N!)

打赏