今天是LeetCode第28篇，依然是全排列的問題。

如果對全排列不熟悉或者是最近關注的同學可以看一下上一篇文章：

LeetCode46 回溯算法求全排列，這次是真全排列

LeetCode就是喜歡這樣，把類似的問題放在一起，讓你刷的時候一起刷，從而更加深刻地理解。今天的問題同樣是全排列，不過稍稍不同的是，我們有一個限制條件不一樣，給定的元素當中可能存在重複。但是元素存在重複，我們並不想最後的結果也出現重複，這個時候應該怎麼辦？

舉個例子，比如我們有一個排列是[1, 2, 2].

它的所有排列是[1, 2, 2], [2, 1, 2], [2, 2, 1]，但是注意，在之前的做法當中，我們把所有的元素看成是unique的，但是現在這個條件被破壞了。顯然我們需要在實現全排列的基礎上解決這個問題。

無腦解決

解決的方法有兩種，第一種是無腦解決。是的你沒有看錯，因為我們分析一下就會發現next_permutation循環的方法在這題當中仍然奏效，原因也很簡單，因為我們每次用next_permutation求得字典序+1的下一個排列的時候，顯然已經去除了重複元素的情況。為什麼？因為同樣元素換位置字典序是不會變化的。

比如下圖當中，我們更換兩個2的順序，整個序列的字典序是沒有變化的，要使得字典序變化一定要交換不同的元素。所以這個解法是可行的。

next_permutation是返回當前序列字典序+1的序列的算法，這個算法在之前的文章當中出現過，所以我就不贅述它的原理了，如果你不記得或者是忘記了的話，可以點擊下方的鏈接回顧一下：

LeetCode 31：遞歸、回溯、八皇后、全排列一篇文章全講清楚

這個解法和上一題的最後一個解法完全一樣，連改動都不需要，我們直接把代碼copy過來把函數名匹配上就可以提交了。這也是我說這道題無腦的原因。

class Solution:
    def get_next(self, nums: List[int]):
        """
        Do not return anything, modify nums in-place instead.
        """
        # 長度
        n = len(nums)
        # 記錄圖中i-1的位置
        pos = n - 1
        for i in range(n-1, 0, -1):
            # 如果降序破壞，說明找到了i
            if nums[i] > nums[i-1]:
                pos = i-1
                break
                
        for i in range(n-1, pos, -1):
            # 從最後開始找大於pos位置的
            if nums[i] > nums[pos]:
                # 先交換元素，在進行翻轉
                nums[i], nums[pos] = nums[pos], nums[i]
                # 翻轉[pos+1, n]區間
                nums[pos+1:] = nums[n:pos:-1]
                return False
        return True
        
        
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        ret = []
        # 從小到大排序，獲得最小排列
        nums = sorted(nums)
        ret.append(nums.copy())
        # 如果還有下一個排列則繼續調用
        while not self.get_next(nums):
            # 要.copy()是因為Python中存儲的引用，如果不加copy
            # 會導致當nums發生變化之後，ret中存儲的數據也會變化
            ret.append(nums.copy())
        return ret

回溯法

顯然重複之前的工作並不能讓我們變得更強，所以我們還是要回到正解上來。在之前的文章我們知道，生成全排列的通常做法是使用回溯法。那麼如果使用回溯法我們怎麼解決重複元素的問題呢？

還是老慣例，我們要解決問題，首先來分析問題，我們知道重複的元素會干擾全排列生成的算法，那麼它為什麼會干擾，是怎麼干擾的？

在回溯法當中，我們是順序遍歷位置，然後枚舉放置的元素。於是我們大概可以想出兩種可能導致重複的情況。

我們先來看情況1，情況1很簡單，就是同一個位置放入同樣元素的情況。比如我們原數組當中有兩個4，我們在放置的過程當中放入第一個4和第二個4的情況是一樣的。顯然這就重複了，我們可以參考下下圖，我們給當下所有的選擇編號，選擇2和選擇3是等價的，兩者只能選一個。

第二種情況也比較容易想明白，還是同樣的例子，我們給數組當中的兩個4編號，一個編號是，一個是，我們會發現對於兩個位置，我們先放第一個再放第二個和先放第二個再放第一個是重複的。

表面上來看情況是這兩種，但是如果深入分析會發現這兩種情況其實說的是一回事，結果出現重複都是由於全排列的時候元素出現不穩定造成的。

這裡的「穩定「其實是一個排序算法當中的術語，我們經常會討論某一個排序算法是穩定的，某一個不是。這個穩定是什麼意思呢，其實就是指的元素的相對順序。比如在上面這張圖當中的兩個4，如果在排序的結果當中，後面一個4有可能出現在第一個4的前面，那麼就說明這個算法是不穩定的，同樣，如果不會出現這樣的情況，那麼可以說這個算法是穩定的。

同樣，如果我們能保證執行全排列的時候元素的穩定性，那麼這個問題就解決了。表面上看這似乎是一個優化問題，其實不然，考察的是穩定性這個概念。

如果能想到穩定性這點，離解決已經很近了。我們要保證穩定性，也就是說對於當前元素，我們需要保證前面的同元素已經放置了，那麼在一個排列中，相同元素的擺放位置應該是遞增的。我們用map記錄每一個元素最後一次擺放的位置，控制它在往下遞歸的過程當中遞增即可。

比如當數組當中有兩個4的時候，第一個4如果還沒有擺放，那麼第二個4也不能擺。但是由於我們在判斷要不要擺放第二個4的時候，並不知道前面是否還有其他的4，所以我們只能倒過來，判斷在擺放第一個4的時候，是不是已經放過了後面的4，如果是的話，那麼這個操作不能執行。用語言描述這個邏輯有點繞，我們來看下圖就明白了：

我們擺放了第一個4之後，map[4] = 4，記錄的是擺放的4的下標，當我們枚舉放置第一個4的時候，發現已經放置的4下標大於當前，說明非法，放置了會引起重複。

還有一個問題是當我們回溯的時候，需要重置map里的值，比如：

在一次遞歸當中，我們放置了兩個4，放了第二個4之後，map[4] = 4，當我們回溯彈出第二個4的時候，這個時候的map[4]應該是多少？

答案不難，應該是1，也就是第一個4的下標。所以我們在遞歸的時候，在更新map之前，需要記錄一下之前的值，方便回溯的時候恢復。

我們整理一下，思路可以得到代碼：

class Solution:
    def dfs(self, nums, n, i, states, cur, ret, flag):
        if i == n:
            ret.append(cur.copy())
            return
        for p in range(n):                
            # 遍歷所有元素
            # 如果p元素已經放置過了，或者是已經放置了更後面的同元素
            # 跳過
            if flag[p] or (nums[p] in states and states[nums[p]] >= p):
                continue
            # 當前位置放置p
            cur.append(nums[p])
            # 更新之前，記錄之前的值
            tmp, states[nums[p]] = states[nums[p]] if nums[p] in states else -1, p
            # flag[p]置為True
            flag[p] = True
            # 遞歸
            self.dfs(nums, n, i+1, states, cur, ret, flag)
            # 回溯
            cur.pop()
            flag[p] = False
            # 恢復遞歸之前的值
            states[nums[p]] = tmp 
            # states.remove((i, nums[p]))
        
        
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        ret = []
        n = len(nums)
        # 記錄元素i有沒有放置過
        flag = [False for _ in range(n)]
        self.dfs(nums, n, 0, {}, [], ret, flag)
        return ret

改進

上面這個方法其實有點複雜，理解起來有很多細節，一個比較蛋疼的點就是我們用了map去記錄了位置，由於要更新map，所以還需要記錄之前的值，還需要判斷元素不在map當中的情況。並且map的查找存在開銷，那麼我們能不能不用map呢？

在想怎麼不用map的替代方案之前，我們需要先搞清楚，我們為什麼要使用map？

這個問題問的並不是一個充分問題，而是一個必要問題，不是用map解決了什麼問題，而是我們為什麼只能用map不可呢？

因為map是一個容器，它能存儲數據。對於一個元素t來說，我們並不知道它在數組nums當中之前出現的位置是哪裡，我們也並不知道這些之前出現的t有沒有被放入當前的排列里。我們用map記錄下t的下標，本質原因是這個。map只是我們實現這個功能的手段，不是目的。

所以我們如果不想使用map，必須要保證能夠知道每一個元素的擺放位置才可以。要做到這點其實並不難，我們只需要對nums排序就好了。排序之後，所有相同的元素都會挨在一起。那麼，對於位置p來說，我們只需要判斷如果nums[p-1] 等於 nums[p]的話，必須要flag[p-1]等於true，也就是說對於元素v來說，它前面一位如果是v必須要放置好，才能放置當前的v，否則就是非法的。這樣每一個v都限制前一個v，就保證了所有的v不會起衝突。這是一種鏈式限制的思想。

通過這種方法，我們就可以拋棄掉map的使用，進而極大地提升效率。

想清楚了原理之後，代碼非常簡單：

class Solution:
    def dfs(self, nums, n, i, cur, ret, flag):
        if i == n:
            ret.append(cur.copy())
            return
        for p in range(n):                
            # 遍歷所有元素
            # 如果p元素已經放置過了，或者
            # 如果nums[p-1] == nums[p] 並且flag[p-1] 是False
            # 跳過
            if flag[p] or (p > 0 and nums[p-1] == nums[p] and not flag[p-1]):
                continue
            # 當前位置放置p
            cur.append(nums[p])
            # flag[p]置為True
            flag[p] = True
            # 遞歸
            self.dfs(nums, n, i+1, cur, ret, flag)
            # 回溯
            cur.pop()
            flag[p] = False
        
        
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        ret = []
        n = len(nums)
        # 記錄元素i有沒有放置過
        nums = sorted(nums)
        flag = [False for _ in range(n)]
        self.dfs(nums, n, 0, [], ret, flag)
        return ret

你看，我們只需要排序，也不需要引入新的數據結構，就可以完美地解決這個問題。其實很多時候，解決問題的途徑有很多種，能不能想到更好的解法除了取決於能力之外，更重要的還是對問題的理解。

這道題也是一個Medium的問題，總體來說難度並不大。如果可以不看標程，獨立通過這道題，就說明對全排列這個問題的思考已經比較到位了。

今天的文章就是這些，如果覺得有所收穫，請順手點個關注或者轉發吧，你們的舉手之勞對我來說很重要。