本文为个人解题思路整理，水平有限，有问题欢迎交流
概览
这题想做出来其实很简单，但是可以通过剪枝不断的优化性能，又是一道表面深搜实则优化的题
难度：中等
核心知识点：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个数字开始尝试
- 检查数字x是否满足下面全部条件，若是则证明不可使用，尝试序列的下一个数字
- 前面有数字
- x前面数字未被使用
- x前面数字与x相等
- 将x使用次数加1
- 将排列中的第1位设置为x
- 继续对排列第2位暴力深搜
- 将x的使用次数减1
- 继续尝试序列的下一个数字
完整代码
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
个人站点：在搭了在搭了。。。（右键 - 新建文件夹）
