LeetCode 筆記 - 47. Permutations II

Posted on Edited 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:

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

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

第一個數字被選中

第二個數字被選中

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

只有第二個數字被選中

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

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

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

而最後要處理的事情就是
在一開始利用 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
27
class Solution:
    def dfs(self, data, data_length, visited, result):
        if data_length == len(visited):
            self.result.append(result[:])
            return

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

            self.dfs(data, data_length, visited + [i], result + [data[i]])

    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        
        l = len(nums)
        if l <= 1:
            return [nums]
        
        nums.sort()
        self.result = []
        
        self.dfs(nums, l, [], [])
        
        return self.result