Permutations II【Medium】【Python】【 retrograde 】

Problem

LeetCode

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

Input, the Output,1,2 [1] : [,1,2 [1], [1, 2, 1], [2,1,1]]Copy the code

The problem

Power button

Given a sequence that can contain repeating digits, return all non-repeating permutations.

Example:

Input: [1,2] output: [[1,1,2], [1,2,1]]Copy the code

Train of thought

Method a

recursive

Refer to LeetCode 0046, just add a check that the path is not repeated. I.e., the path is notinRes.Copy the code
Python3 code
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        # solution one: recursion
        res = []
        self.dfs(nums, res, [])
        return res
    
    def dfs(self, nums, res, path):
        if not nums and path not in res:  # path should be unique
            res.append(path)
        else:
            for i in range(len(nums)):
                self.dfs(nums[:i] + nums[i + 1:], res, path + [nums[i]])
Copy the code
Method 2

back

1. Valid result: The SOL length is equal to the NUMS length. 2. Retrospective scope and answer update. 3. Pruning conditions: a. Used can not be used again, to pruning. B. The current element is the same as the previous element, and the previous element is not used, also prune.Copy the code
Python3 code
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        # solution two: backtracking
        nums.sort()  # sort at first
        self.res = []
        check = [0 for _ in range(len(nums))]

        self.dfs([], nums, check)
        return self.res
    
    def dfs(self, sol, nums, check):
        # 1.valid result
        if len(sol) == len(nums):
            self.res.append(sol)
            return
        
        for i in range(len(nums)):
            # 3.pruning
            if check[i] == 1:  # used
                continue
            if i > 0 and nums[i] == nums[i - 1] and not check[i - 1] :continue

            # 2.backtrack and update check
            check[i] = 1
            self.dfs(sol + [nums[i]], nums, check)
            check[i] = 0  # after backtracking, should update check[i]
Copy the code

The code address

Making a link

reference

Sammy antithesis