觸類旁通 從回溯法理解直線排列的本質 Permutation_Leetcode #46 #47

Jean-Louis Paulin on Unsplash

這篇文章，會帶大家快速回顧DFS+回溯法框架(還沒看過或想複習的可以點連結進去)。

用DFS+回溯法框架，解開 直線排列Permutations 的全系列題目。

幫助讀者鞏固DFS+回溯法框架這個重要的知識點。

回顧 DFS+回溯法框架

白話的意思

# 列舉所有可能的情況，遞迴展開所有分支，把符合條件的分支納入解答。

演算法框架 + 虛擬碼

def backtrack( parameter ):

	# 終止條件
	if stop condition:
		save result if needed						# 有需要的話，儲存當下的狀態作為結果​
		return
	
	# 通則​	
	for each possible next selection # 列出所有選擇
		make a selection									# 做出一個選擇​
		backtrack( updated patameter )	# 遞回展開下一層​
		undo selection										# 撤銷選擇，回到原始狀態，準備做下一個選擇​

	return	

直線排列 I_Permutations

目標

輸入n個相異的元素，返回這n個元素的直線排列。

演算法 DFS + 回溯法

通則

怎樣叫做直線排列?

其實就是每個元素輪流當排頭，並且依照同樣的規則遞迴展開。

1當排頭，剩下的元素遞迴展開做直線排列

2當排頭，剩下的元素遞迴展開做直線排列

...

n當排頭，剩下的元素遞迴展開做直線排列

終止條件

什麼時候代表已經做完直線排列了?

當已經把所有元素都用完了，這時候這條分支的直線排列的展開已經完成，也結束了。

程式碼 DFS + 回溯法

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        
        result = []

        def perm( start):

            if start == len(nums):
                result.append( nums.copy() )
                return
            
            for i in range(start, len(nums) ):
                nums[start], nums[i] = nums[i], nums[start]
                perm(start+1)
                nums[start], nums[i] = nums[i], nums[start]
            return

        #========================
        perm( start = 0 )
        return result

直線排列 II_Permutations

目標

輸入n個的元素，裡面可能有重複元素，返回這n個元素的直線排列。

演算法 DFS + 回溯法 + 集合排除重複

通則和終止條件其實和前一題相同，這邊不重複敘述。

關鍵在於，如何保證不會重複製造相同的直線排列?

有一個直覺的想法，什麼資料結構可以記錄看過的資訊，用來去除重複?

就是Set集合，把看過的元素存到集合裡面，之後遇到同樣的元素就直接跳過即可。

程式碼 DFS + 回溯法 + 集合排除重複

class Solution:

    def permuteUnique(self, nums: List[int]) -> List[List[int]]:

        def perm(start):

            ## Base case aka stop condition
            if start == len(nums):
                result.append(nums.copy())
                return 
            
            # Avoid repetition
            seen = set()

            ## General cases
            for i in range(start, len(nums)):
                if nums[i] not in seen:
                    seen.add(nums[i])

                    nums[start], nums[i] = nums[i], nums[start]
                    perm(start+1 )
                    nums[start], nums[i] = nums[i], nums[start]
            return 
        #-----------------------------------------
        result = []
        perm( start = 0)
        return result

另解，用字典去排除重複

用字典來記錄每個元素的出現次數，字典的鍵值本身就具有排除重複的性質。
排列過程中，每排一次，當下數字的出現次數就減一，排到出現次數用完為止。

程式碼 DFS + 回溯法 + 字典排除重複

class Solution:

    def permuteUnique(self, nums: List[int]) -> List[List[int]]:

        def perm(start, cur):

            ## Base case aka stop condition
            if start == len(nums):
                result.append( cur )
                return 
            
            ## General cases
            for number in occurrence:

                # Avoid repetition
                if occurrence[ number ] > 0:
                    occurrence[ number ] -= 1
                    perm(start+1, cur + [ number ] )
                    occurrence[ number ] += 1
            return 
        #-----------------------------------------
        occurrence = Counter(nums)
        result = []
        perm( start = 0, cur = [])
        return result

結語

好，今天一口氣介紹了最精華的部分，

通用的DFS+回溯法的枚舉框架，還有相關的直線排列衍伸變化題與演算法建造，

希望能幫助讀者、觀眾徹底理解它的原理，鞏固知識點。

並且能夠舉一反三，洞察其背後的本質和了解相關的應用領域！

感謝收看囉! 我們下篇文章再見~