Article From:https://www.cnblogs.com/zzq-123456/p/9969854.html

@author: ZZQ
@software: PyCharm
@file: permuteUnique.py
@time: 2018/11/16 13:34
Requirement: Given a sequence of repetitive numbers, return all non-repetitive full permutations.
Example:
Input: [1, 1, 2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
Thought: Deep search, and then remove the unsatisfactory conditions
Deduplication process:
1. Every time you search down, you remove the parent node element
2. Make a mark for each element to indicate whether the current element has been used or not, and if it has been used, end the downward search.
3. Judge whether the adjacent same element has been used or not, and if it has been used, skip the element.

import copy
class Solution():
    def __init__(self):
        tt_ans = []
        pass

    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ans = []
        temp_ans = []
        nums.sort()
        length = len(nums)
        if length == 0 or nums == []:
            return []
        flag = []
        for i in range(length):
            flag.append(0)
        cur_length = 0
        start_index = -1
        self.dfs(temp_ans, start_index, nums, flag, cur_length, length, ans)
        return ans

    def dfs(self, temp_ans,start_index, nums, flag, cur_length, length, ans):
        if cur_length == length:
            tt_ans = copy.deepcopy(temp_ans)
            ans.append(tt_ans)

        else:
            for i in range(length):
                if i > 0 and nums[i] == nums[i - 1] and flag[i - 1] == 1:
                    continue
                if i != start_index and flag[i] == 0:
                    temp_ans.append(nums[i])
                    flag[i] = 1
                    self.dfs(temp_ans, i, nums, flag, cur_length+1, length, ans)
                    temp_ans.pop()
                    flag[i] = 0
Link of this Article: Leetcode: Full Arrangement II

Leave a Reply

Your email address will not be published. Required fields are marked *