觸類旁通: 用 DFS回溯法框架 解 組合數之和 全系列題。

Edge2Edge Media null on Unsplash

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

用DFS+回溯法框架，解開 組合數之和 Combination Sum 的全系列題目。

幫助讀者鞏固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__Combination Sum - LeetCode

題目說candidates提供的數字可以重複選，請列出所有總和為target的組合情況。

初始條件在哪呢?

其實有兩個。

1. 當target 扣到最後等於0的時候，代表沿路挑的數字剛好總和為目標值。這時候當下的組合是一組解，納入答案。
2. 當target 扣到最後小於0的時候，代表沿路挑的數字總和太大了，可以直接停下來，不用再往下搜索了。

通則呢?

列舉candidate提供的每個數字，製造出所有可能的組合。
並且遞迴到下一層的時候，傳遞給下一層的index留在原地，提供重複選擇的可能。

現在初始條件和通則都具備了，寫成DFS+回溯法的程式碼:

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:

        result = []

        def dfs(start, cur=[], target=0):
            
            # Base case
            if target < 0:
                # Early stop
                return

            elif target == 0:
                # Perfect match
                result.append( cur[::] )
                return

            # General cases
            for i in range(start, len(candidates)):
                cur.append( candidates[i] )
                dfs(i, cur, target - candidates[i])
                cur.pop()
            return

        # ---------------------
        dfs(start=0, cur=[], target=target)
        return result

組合數之和 II__Combination Sum II - LeetCode

題目說candidates提供的數字，同樣的數字只能選一次，
請列出所有總和為target的組合情況。

前處理:

先將candidates由小到大做排序，方便之後避免重複挑選的過濾。

初始條件在哪呢?

其實有兩個。

1. 當target 扣到最後等於0的時候，代表沿路挑的數字剛好總和為目標值。這時候當下的組合是一組解，納入答案。
2. 當target 扣到最後小於0的時候，代表沿路挑的數字總和太大了，可以直接停下來，不用再往下搜索了。

通則呢?

列舉candidate提供的每個數字，製造出所有可能的組合。

挑選數字時，只有第一次遇見的數字，或者相異的數字才能被納入。

並且遞迴到下一層的時候，傳遞給下一層的index往前移動，不提供重複選擇的可能。

現在初始條件和通則都具備了，寫成DFS+回溯法的程式碼:

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:

        result = []

        def dfs(start, cur=[], target=0):
        
							# Base case
            if target < 0:
                return 
            if target == 0:
                result.append( cur[::] )
                return
							
							# General Cases
            for i in range(start, len(candidates)):

                if i == start or (candidates[i] != candidates[i-1]):
                    cur.append( candidates[i] )
                    dfs(i+1, cur, target - candidates[i] )
                    cur.pop()

            return

        # ----------------------------------------
        candidates.sort()
        dfs(start=0, cur=[], target=target)
        return result

和第一題很像，只是多了禁止重複的判斷和排序前處理。

組合數之和 III__Combination Sum III - LeetCode

題目說1~9之中，選k個相異的數字，

請列出所有總和為target的組合情況。

初始條件在哪呢?

其實有兩個。

1. 當target 扣到最後等於0 而且 剛好挑了k個相異數字的時候，代表沿路挑的數字剛好總和為目標值。這時候當下的組合是一組解，納入答案。
2. 當target 扣到最後小於0的時候，代表沿路挑的數字總和太大了，可以直接停下來，不用再往下搜索了。

通則呢?

列舉candidate提供的每個數字，製造出所有可能的組合。

挑選數字時，只有相異的數字才能被納入。

並且遞迴到下一層的時候，傳遞給下一層的index往前移動，不提供重複選擇的可能。

現在初始條件和通則都具備了，寫成DFS+回溯法的程式碼:

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

        def dfs(i, cur=[], target=0):

							# Base case
            if target < 0:
                return

            elif target == 0 and len(cur) == k:
                result.append( cur[::] )
                return

							# General cases
            for num in range(i, 10):
                cur.append( num )
                dfs( num+1, cur, target - num)
                cur.pop()
            return

        #=================================
        dfs(i=1, cur=[], target=n)
        return result

想一下，為什麼這題不用排序做前處理了?

因為題目已經說從1~9裡面挑數字，1~9先天就已經是從小到大排序了。

再想一下，為什麼這題程式碼裡面不用加if 去過濾重複的數字?

因為題目已經說從1~9裡面挑數字，1~9先天就已經彼此不重複的數字了。

組合數之和 IV__Combination Sum IV - LeetCode

題目說nums提供的數字，同樣的數字可以重複選擇，

請列出所有總和為target的排列方法數(只要知道方法數即可，不用回傳具體排列內容)。

初始條件在哪呢?

其實有兩個。

1. 當target 扣到最後等於0的時候，代表沿路挑的數字剛好總和為目標值。這時候當下的組合是一組解，納入答案。
2. 當target 扣到最後小於0的時候，代表沿路挑的數字總和太大了，可以直接停下來，不用再往下搜索了。

通則呢?

列舉nums提供的每個數字，製造出所有可能的排列。

挑選數字時，可以重複選則。

並且遞迴到下一層的時候，傳遞給下一層的index歸零，提供重複選擇的可能。

現在初始條件和通則都具備了，寫成DFS+回溯法的程式碼:

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:

        ## DP table
        # key: target
        # value: method count sum up to target
        dp = {}

        def dfs(target=0):

            if target < 0:
                # Base case
                return 0

            elif target in dp:                
                # Look-up DP table
                return dp[target]

            elif target == 0:                
                # Base case
                dp[0] = 1
                return 1

            # General cases
            count = 0
            for i in range(0, len(nums)):
                count += dfs( target - nums[i] )
                
            dp[target] = count
            return count

        # ---------------------
        return dfs(target=target)

想一下，為什麼這題不用cur參數了?

因為這題只是要問排列方法數，不用回傳具體的排列情況。

想一下，為什麼這題不用start參數，而且index每層遞回要歸零?

因為這題可以重複選擇，而且又是問排列方法數。
排列的話，順序不同就視為兩種不同的合法方法數。

例如(1,2,2) 和 (2,1,2) 都是總和為5的合法排列。

結語

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

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

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

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

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