47. 全排列 II 给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ]
这道题和上一题的不同之处在于，这道题有重复的数字，重复的数字在排列的时候会出现重复的排列，这个时候需要剪枝操作。
剪枝的过程也是灵性。首先对列表进行排序，如果有相同的数值，那么我们两个相同的数字是在一起的，如果是第一次进行排列，那么所有相同的字符都会被添加到输出。再之后的回溯过程中，例如【1，1，2】如果第一遍已经输出，第二遍再回溯时，我们开始的数字是第二个1，这个时候再添加第一个1就已经和之前的答案重复了。
所以这里有一个剪枝的过程，剪枝的条件为 i > 0，因为是要 nums[i] 与 nums[i-1]比较，左边的上一个数字比较，如果上一个数字已经被使用过，说明这是头遍循环，可以添加第二个重复的数字到输出。但是如果第一个数字没被使用过，而第二个数字将要被使用，这个时候由于是一个全排列，那么没有被使用过的第一个数字是会被加入输出的，由于我们首先对列表进行过排序，这种情况肯定是在一个数字被首先使用之后才出现的，所以这种情况需要剪枝。
from typing import List class Solution: def permuteUnique(self, nums: List[int]) -> List[List[int]]: length = len(nums) output = [] nums = sorted(nums) # nums.append('.') def backtrack(count, out, stack):#构建回溯函数 if count == length :#确定退出条件，即得到有效解的条件 output.append(out.copy()) return for i in range(length):#因为序列长度有多少次就会循环多少次 if i in stack: continue if i > 0 and nums[i] == nums[i-1] and i-1 not in stack: continue out.append(nums[i])#将这个字符添加进输出 stack.append(i) backtrack(count+1, out, stack)#回溯 out.pop()#弹出上一次加入到输出的字符 stack.pop() backtrack(0, [], []) return output if __name__ == "__main__": s = Solution() print(s.permuteUnique([2,2,3]))