题目
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
例：
输入：nums = [1,1,2]
输出：[[1,1,2], [1,2,1], [2,1,1]]
方法：回溯、递归
思路类似 46. 全排列，不同之处在于本题数组 nums 中可能存在重复元素值
- path 表示单一的排列方式，result 表示所有可能的排列方式。use 表示数组中的元素是否已被使用，1 表示已被使用，0 表示未被使用
- 因为可能存在元素值相同的情况，所以需要对数组 nums 进行排列
backtrack 函数：回溯
- 因为对数组进行排列，那么 path 内包括所有 nums 元素时，即 path 的长度等于 nums 的长度，完成一次排列，将其加入 result
- 因为首位为不同元素表示不同的排列方式，所以每层的循环都是从零开始。但是由于不能重复使用同一元素，那么需要对元素是否使用过进行判断，当选取的元素并未使用过时，即 use[i] = 0，才可继续
- 若选取的元素并非数组 nums 的第一个元素，且该元素与前一个元素的值相同，且前一个元素在该 path 中并未使用，由于每次的循环都是从零开始，即选取元素的前一个元素 nums[i-1] 已实现过和该元素相同的排列，那么跳过此次循环
例：下图的树的第二层，当第一个数均为 1 时，第二个可以被剪枝
class Solution(object):
def permuteUnique(self, nums):
path, result = [], []
use = [0] * len(nums)
nums.sort()
def backtrack(nums):
if len(path) == len(nums):
result.append(path[:])
return None
for i in range(len(nums)):
if not use[i]:
if i > 0 and nums[i-1] == nums[i] and not use[i-1]:
continue
use[i] = 1
path.append(nums[i])
backtrack(nums)
path.pop()
use[i] = 0
backtrack(nums)
return result
参考
代码相关：https://programmercarl.com/0047.%E5%85%A8%E6%8E%92%E5%88%97II.html
