47..md

47. Permutations II

{% tabs %} {% tab title="优化" %}

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        visited = [-1] * len(nums)
        self.dfs(0,nums,[],res,visited)
        return res

    def dfs(self,idx,nums, path, res,visited ):
        if  idx == len(nums):
            res.append(path[:])
            return 

        for i in range(len(nums)):
            if visited[i] == -1:##没访问过
                if i > 0 and nums[i] == nums[i-1] and visited[i-1] == 1: continue
                visited[i] = 1
                path.append(nums[i])
                self.dfs(idx + 1, nums,path,res,visited)
                path.pop()
                visited[i] = -1

{% endtab %}

{% tab title="Python暴力" %}

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res = []
        self.helper(nums, res, [])
        return res
    ## 暴力不是说不好，只是它处理问题的方式不正确
    ## 对于 重复元素的处理是线性的
    ## 对于操作过的元素，增大了空间复杂度
    def helper(self, nums, res, path):
        if not nums and path not in res:
            res.append(path)
        else:
            for i in range(len(nums)):
                self.helper(nums[:i] + nums[i+1:], res, path + [nums[i]])

{% endtab %} {% endtabs %}