LeetCode 筆記 - 47. Permutations II

Posted on

題目在此 47. Permutations II

給定一個重複數列，計算出所有不重複排列

解題思維

這題就 46. Permutations 的變形題，筆記在此

比較不一樣的地方是這題的給定的數列允許有 重複 的數值

所以我們在遞迴的過程中就需要使用一些小技巧來避免
曾經遞迴過的重複組合

在這裡講解一下關鍵程式碼

1
2
if i != 0 and data[i] == data[i - 1] and i - 1 not in visited:
    continue

其中

1
data[i] == data[i - 1]

這裡很好理解，就是前後相同
再來就是需要想一下的地方

1
i - 1 not in visited:

前一格並沒有拜訪過？這個判斷代表的意義是什麼？

我們來模擬一下遞迴的情況
黑色不相關，白色是我們相鄰的重複數字
image 27

第一個數字被選中
image 28

第二個數字被選中
image 29
我們可以看到，這時候兩個重複的數字組合 第一次出現

只有第二個數字被選中
image 30

這時候因為遞迴式會找還沒有被採訪過的格子下去遞迴
可以想見等一下發生的事情就是 第一個數字又被選中

這時候兩個重複的數字組合就會 第二次出現

而這就是我們不想看到的情況
所以一但前一個數字與當下數字相同而前一個數字沒有被選中的情況發生
我們需要跳過，以避免重複的組合出現

而最後要處理的事情就是
在一開始利用 Sorting 讓相同的數字放在一起

完成✅

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:

        size = len(nums)

        visited = set()

        result = []
        def dfs(values):
            if len(values) == size:
                result.append(values)

            for i in range(size):
                if i in visited:
                    continue
                if i != 0 and nums[i - 1] == nums[i] and i - 1 not in visited:
                    continue

                visited.add(i)
                dfs(values + nums[i:i+1])
                visited.remove(i)
        
        nums.sort()
        dfs([])

        return result
image 106

也許你也會想看看