leetcode 47 全排列2

使用递归，剪枝

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        result=[]
        def dfs(i,path,visit,result):
            if i==len(nums):
                if path not in result:
                    result.append(path)
                    return 
            for j in range(len(nums)):
                if j in visit:continue

                dfs(i+1,path+[nums[j]],visit+[j],result)

        dfs(0,[],[],result)
        return result

通过将数组进行排序，然后判断这个数组中之前的数字是由有过遍历，进行剪枝。

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        result=[]
        def dfs(i,path,visit,nums,result):

            if i==len(nums):
                result.append(path)
                return 

            for j in range(len(nums)):
                if j in visit:continue
                if j>=1 and  nums[j]==nums[j-1] and j-1 not in  visit:
                    continue

                dfs(i+1,path+[nums[j]],visit+[j],nums,result)

        dfs(0,[],[],sorted(nums),result)
        return result

回溯

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        result=[]
        def dfs(i,path,visit,nums,result):

            if i==len(nums):
                result.append(path[:])
                #path.pop()
                return 

            for j in range(len(nums)):
                if j in visit:continue
                if j>=1 and  nums[j]==nums[j-1] and j-1 not in  visit:
                    continue
                path.append(nums[j])
                visit.append(j)
                dfs(i+1,path,visit,nums,result)
                path.pop()
                visit.pop()

        dfs(0,[],[],sorted(nums),result)
        return result