LeetCode0047.PermutationsIIFullArrangementII【Medium】【Python】【Backtracking】问题LeetCode给定一个可能包含重复的数字集合，返回所有可能的唯一排列。例子：输入：[1,1,2]输出：[[1,1,2],[1,2,1],[2,1,1]]问题Leetie给定一个可以包含重复数字的序列，返回所有不重复的全排列。例子：输入：[1,1,2]输出：[[1,1,2],[1,2,1],[2,1,1]]思路解法1递归参考LeetCode0046，直接加上就是足以判断路径不重复。即：路径不在资源中。Python3代码类解决方案：defpermuteUnique(self,nums:List[int])->List[List[int]]:#解决方案一：递归res=[]self.dfs(nums,res,[])returnresdefdfs(self,nums,res,path):ifnotnumsandpathnotinres:#路径应该是唯一的res.append(path)else:foriinrange(len(nums)):self.dfs(nums[:i]+nums[i+1:],res,path+[nums[i]])解法二回溯回溯三步：1、有效结果：sol的长度等于nums的长度。2.回溯范围和答案更新。三、修剪条件：用过的不能重复使用，必须修剪。b.当前元素与前一个元素相同，前一个元素没有被使用过，所以也需要剪枝。Python3代码类解决方案：defpermuteUnique(self,nums:List[int])->List[List[int]]:#解决方案二：回溯nums.sort()#首先排序self.res=[]check=[0for_inrange(len(nums))]self.dfs([],nums,check)returnself.resdefdfs(self,sol,nums,check):#1.validresultiflen(sol)==len(nums):self.res.append(sol)returnforiinrange(len(nums)):#3.修剪ifcheck[i]==1:#usedcontinueifi>0andnums[i]==nums[i-1]andnotcheck[i-1]:continue#2.backtrackandupdatecheckcheck[i]=1self.dfs(sol+[nums[i]],nums,check)检查[i]=0#回溯后，应该更新check[i]代码地址GitHub链接参考sammy解决方案
