【算法刷题】全排列 II

本文为个人解题思路整理，水平有限，有问题欢迎交流

概览

这题想做出来其实很简单，但是可以通过剪枝不断的优化性能，又是一道表面深搜实则优化的题

难度：中等

核心知识点：DFS(回溯) + 数据结构

题目来源

力扣：https://leetcode-cn.com/problems/permutations-ii/

题目要求

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

样例

输入1：

[1,1,2]

输出1：

[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

解题思路

第一想法，暴力深搜+回溯，按顺序搜索每个位置的每个可能数字，但是如何保证不重复呢
不重复第一想法是状态压缩，然后存进图，但是明显不可取，因为没有限制数字的大小
继续考虑如何去重复，得到一个思路：在一个排列中，两个相等的数字是可以互换的，对吧

举个例子，存在两个数字a和b相等，那么排列...a...b...与...b...a...是完全一样的对吧，也就是两个序列重复了

那么，如果给出的序列中，a在b前面，...a...b...是合法的，...b...a...是不合法的，因为重复了

再换个角度想一下，其实...b...如果不使用a是合法的，但...b...a...就不合法了，其实关键在于不能使用a

现在问题就简单了，只需要检查a的存在即可，即：对于数字b，是否存在一个数字a，满足条件：a在b之前，且a和b相等，且a未被使用

但是要注意，如果a存在，不合法的其实是b，因为全排列必须使用所有数字，也就是必须使用a，也就是现在的b后面无论怎么排都是不合法的

总结一下就是，在使用数字b时，检查b前面是否存在与b相等，且未被使用的数字
显然可以用map或者set来检查数字是否被使用，检查相等直接往前搜索即可，简单暴力

现在基本的解题思路定下来了，开始优化

基本思路：
- 暴力深搜+回溯，按顺序搜索每个位置的每个可能数字
- 搜索某个位置的可能数字b时，确认这个数字在前面是否存在相等且未被使用的数字a，若有，那么这个数字b不可用
优化：因为深搜一个可能之后要回溯，那么使用栈操作最后一个元素会方便的多（稍微比list方便，但其实也没多少）
优化：仔细想一下，其实这个序列的初识顺序并没有意义，反正是要考虑所有的排列，那么如果在一开始就将序列进行排序（递增或递减），那么就可以将相等的数字聚集到一起，往前搜索与自己相等的数字会快很多很多

比如原本是 1,3,4,5,1,2，考虑第二个1的时候，要往前找4位找到与自己相等的

排序之后是1,1,2,3,4,5只需要往前找一位即可，如果出现与自己不相等的，就证明没有与自己相等的了，可以提前结束检索了

要注意条件是与自己相等且未被使用哦，不只是相等而已

这个时候得到的方案基本如下

对序列进行排序（递增递减均可）
从第一个位置开始暴力深搜，使用回溯挨个尝试序列的每个数字
尝试数字的时候，检查这个数字前面是否有相等的数字，且未被使用，若有，则放弃当前这个数字（因为会重复）
使用map记录被使用过的数字在序列中的位置

一开始我的做法便是如此，但性能一般(5ms)，看了题解发现可以进一步优化

优化：对于序列a,b,c,d,e，如果a,b,c相等，那么对于排列...a...b...c...，这三个数互相换位置都是同一个排列

那么固定这三个数的相对顺序，不允许其他相对顺序出现，那么就能排除掉重复的排列

不妨指定顺序为序列中的顺序，即对于a,b,c满足
- 不允许b出现在a之前
- 不允许c出现在a和b之前
又因为全排列必须使用所有数字，那么等同于
- 使用b之前必须已使用a
- 使用c之前必须已使用b
将这两个条件通用化即，使用数字x之前满足以下条件之一
- x的前面的数字与x不相等
- x前面的数字已被使用

优化完成，开始提出解决方案

解题方案

对序列进行排序（递增递减均可）
从排列的第1位开始暴力深搜
1. 检查排列的长度是否与序列相等，若是，则已搜索到结果，保存结果并返回上一层
2. 从序列的第1个数字开始尝试
3. 检查数字x是否满足下面全部条件，若是则证明不可使用，尝试序列的下一个数字
  - 前面有数字
  - x前面数字未被使用
  - x前面数字与x相等
4. 将x使用次数加1
5. 将排列中的第1位设置为x
6. 继续对排列第2位暴力深搜
7. 将x的使用次数减1
8. 继续尝试序列的下一个数字

完整代码

package com.company;

import java.util.*;

/**
 * @author Echo_Ye
 * @title 力扣47. 全排列 II
 * @description 排列求解
 * @date 2020/9/18 17:26
 * @email echo_yezi@qq.com
 */
public class PermuteUnique {
    public static void main(String[] args) {
        PermuteUnique permuteUnique = new PermuteUnique();
    }

    public PermuteUnique() {
        int[] nums = new int[]{1, 3, 1, 2};
        List<List<Integer>> ans = permuteUnique(nums);
        for (List<Integer> list : ans) {
            for (Integer i : list) {
                System.out.print(i + "    ");
            }
            System.out.println();
        }
    }

    //用于标记是否已被使用
    boolean[] isUsed;
    List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        //初始化之后默认全部为false
        isUsed = new boolean[nums.length];
        //排序
        Arrays.sort(nums);
        //开始递归搜索
        dfs(new ArrayDeque<>(), nums, nums.length, 0);
        return ans;
    }

    /**
     * 递归深搜
     *
     * @param deque  当前排列
     * @param source 数据源
     * @param total  总共数据数量
     * @param cur    当前检索位置
     */
    public void dfs(Deque<Integer> deque, int[] source, int total, int cur) {
        if (cur == total) {
            //保存答案
            ans.add(new ArrayList<>(deque));
        }
        for (int i = 0; i < total; i++) {
            //检查i是否可用
            if (isUsed[i] || (i > 0 && !isUsed[i - 1] && source[i] == source[i - 1])) {
                continue;
            }
            //标记i为已用，且将其添加到排列
            isUsed[i] = true;
            deque.addLast(source[i]);
            //继续下一层dfs
            dfs(deque, source, total, cur + 1);
            //回溯，标记i未用，且将其从排列末尾移除
            isUsed[i] = false;
            deque.removeLast();
        }
    }
}

结果

性能

后记

优势典型的暴力搜索加剪枝，重点在于后面一步一步的优化，我最开始的方案执行用时是5ms，看了题解优化后达到2ms，优化空间还是挺大的

作者：Echo_Ye

WX：Echo_YeZ

Email ：echo_yezi@qq.com

个人站点：在搭了在搭了。。。（右键 - 新建文件夹）