今天是紀錄LeetCode解題的第四十七天

第四十七題題目：Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

給定一個可能包含重複數字的集合nums，回傳所有可能的唯一排列(順序不限)

程式碼

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        used = [False] * len(nums)
        result = []
        dfs(nums,used,[],result)
        return result
def dfs(nums,used,path,result):
    if len(path) == len(nums):
        result.append(path[:])
    for i in range(len(nums)):
        #當前的nums[i]和前一個數一樣時，只有在「前一個相同數」已經被使用過，才能用這個數
        if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
            continue
        if not used[i]:
            used[i] = True
            path.append(nums[i])
            dfs(nums,used,path,result)
            used[i] = False
            path.pop()

這題也是非常簡單，和昨天的文章也就是上一題一樣的概念架構去寫就好，差別在於這次我們要先做排序，並且在遞迴的過程中檢查相同的數字是否被使用過，如果沒有被使用過的話used[i-1] = False反相之後變成True，那麼就會執行continue跳過

以範例一nums=[1,1,2]來說，上一題會輸出兩次[1,1,2]，原因在於以索引0為主去找組合時可以找到[1,1,2]和[1,2,1]，而換索引1去找時也同樣找到這兩個組合，但這題多加的判斷式，會在i=1時，去判斷i=0的值也相同，而此時i=0在回溯過程當中已經變成False，那這時我們就不能再使用索引1的值去找組合