047 全排列，使用排序+回溯算法轻松解决

二哥瞎逼逼：转眼间，已经进入到 9 月中旬了，一些球友已经拿到转正意向或者 oc 了，当然更多的球友还在耐心地准备当中。那今天就来刷一道二哥的 LeetCode 刷题笔记醒一下脑子。

题意

给定一个可包含重复数字的序列 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]]

分析

这道题是 046.全排列 的延续。046.全排列 中没有重复数字，但 047 中有重复元素。

但是，nums的元素顺序并不会影响结果，所以我们不妨把元素从小到大排个序。在之前的题解中，我们知道，排序在很多时候可以减少题解的复杂度。

这道题也是一样的，当我们对 nums 进行排序后，就可以保证相同的数字会相邻，方便我们在回溯过程中跳过重复的数字。

好，来看这个例子：nums = [1,1,2]，如果按照 046.全排列 思路的话，我们会得到这样的结果：

ans = [
[1,1,2],
[1,2,1],
[1,1,2],
[1,2,1],
[2,1,1],
[2,1,1]
]

可以看到，我们得到了重复的结果，但其实我们只要保证同个位置同个元素只被填入一次就可以避免重复，对吧？

然后在回溯和剪枝中，我们使用布尔数组 us...