合縱連橫: DFS+回溯法框架_理解背後的本質

Philippe Van Doninck on Unsplash

這篇文章，會帶著大家複習以前學過的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
		

接下來，我們會用這個上面這種結構，貫穿一些同類型，有關聯的題目

(請讀者、或觀眾留意上面的這種 DFS+回溯法 框架，之後的解說會反覆出現)

剛好以前有錄過教學影片，提供給讀者參考。

子集合 Subsets

子集合怎麼建造呢?

其實就是依序挑選每個元素，每挑一個，就遞回展開後面剩下的元素，反覆進行，直到選完最後一個元素為止。

用DFS+回溯法來解，就變成下面這個樣子

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        
        
        all_subset = []
        bag = []
                
        def makeSubsetFrom( startIndex ):
            
            # Add current subset into final result
            # Note: python object is passing by reference, so we have to make a copy
            all_subset.append( bag[::] )
            
            
            ## Base cases aka stop condition:
            # No more element
            if startIndex == len(nums):
                return
            
            ## General cases
            # Current level, we choouse element on index i
            for i in range(startIndex, len(nums) ):
                
                bag.append( nums[i] )           # put this element into bag
                makeSubsetFrom( i+1 )           # make subset from remaining elements
                bag.pop()                       # undo selection
            
            return
        
        #----------------------------------------
        makeSubsetFrom( startIndex = 0 )
        
        return all_subset

子集合II Subsets II

那假如當初給的輸入裡面，有重複元素怎麼辦?

其實只要多做一個前處理+篩選即可。

先用排序作為前處理，確保所有元素都是排序好的順序。
挑選的時候，只挑第一次遇見的元素，之後重複的就直接跳過不選。

用DFS+回溯法來解，就變成下面這個樣子

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
               
        
        all_subset = []
        bag = []
        
        
        def makeSubsetFrom( startIndex ):
            
            # Add current subset into final result
            # Note: python object is passing by reference, so we have to make a copy
            all_subset.append( bag[::] )
            
            
            ## Base cases aka stop condition:
            # No more element
            if startIndex == len(nums):
                return
            
            ## General cases
            # Current level, we choouse element on index i
            for i in range(startIndex, len(nums) ):
                
                # avoid duplicates
                if (i == startIndex) or (nums[i] != nums[i-1]): 
                    
                    bag.append( nums[i] )           # put this element into bag
                    makeSubsetFrom( i+1 )           # make subset from remaining elements
                    bag.pop()                       # undo selection

            return
        
        #----------------------------------------
        
        # preprocessing, make numbers in ascending order
        nums.sort()
        makeSubsetFrom( startIndex = 0 )
        
        return all_subset
    

組合 Combinations C(n, k)

那假如是C(n, k)，從n個相異元素裡面挑k個的組合呢?

其實也很類似，先造出子集合，再把那些元素數量=k的子集合蒐集起來即可。

用DFS+回溯法來解，就變成下面這個樣子

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:

        result, bag = [], []

        def pick(start):

            if len(bag) == k:
                result.append( bag[::] )
                return

            if start > n:
                return

            for i in range(start, n+1):
                bag.append( i )
                pick(i+1)
                bag.pop()

            return
        # -----------------
        pick(start=1)
        
        return result

和 Subsets 幾乎九成像，只是多了集合大小 == k的判斷。

組合也學會了，那接下來就是好朋友 排列Permutations啦!

排列 Permutations n!

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

結語

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

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

希望能幫助讀者、觀眾徹底理解它的原理，

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

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