遞歸和回溯解決括號匹配問題

• 2020 年 7 月 19 日
• 筆記
• golang, 回溯, 遞歸

遞歸和回溯解決括號匹配問題

遞歸在之前的文章中有提及，有朋友在後台大呼不過癮，剛好又刷到了一道可以用到遞歸的算法題，還是我們的老朋友：匹配有效括號，廢話不多說，先上題目。

數字 n 代表生成括號的對數，請你設計一個函數，用於能夠生成所有可能的並且 有效的 括號組合。

 

示例：

輸入：n = 3
輸出：[
       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]

來源：力扣（LeetCode）
鏈接：//leetcode-cn.com/problems/generate-parentheses

經過分析，這涉及到了兩個關鍵問題：

1. 如何判斷組合成的括號字符串是有效的
2. 如何構建所有可能性的括號字符串。

第一個問題比較容易想通，必須要左右括號成對出現即可。
如果是暴力解法可以考慮把這兩個問題分成兩步去處理好，而如果是用遞歸，肯定是希望每次遞歸的時候不僅創建出排列組合，且這個組合出來的字符串是有效的。

func generateParenthesis(n int) []string {
	return generate(n)
}


func generate(n int) []string {
	cache := map[int][]string{}

	if cache[n] != nil {
		return cache[n]
	}
	var ans []string

	if n == 0 {
		ans = append(ans, "")

	} else {
		for c := 0; c < n; c++ {
			currentLeft := generate(c)
			currentRight := generate(n - c -1)
			for _, value_left := range currentLeft {
				for _, value_right := range currentRight {
					ans = append(ans, "(" + value_left + ")" + value_right)
				}
			}
		}
	}
	cache[n] = ans
	return ans
}

遞歸的關鍵在於找到邊界，也就是分別對左括號和右括號的創建進行遞歸，這樣就能生成出符合條件的字符串。總體來說這次遞歸的解法非常符合人性，條理清晰，也用到一個cache的map來存儲結果，提高執行效率。

其實這道題也可以使用回溯的方法來實現，具體代碼實現如下：

func generateParenthesis2(n int) []string {
	ans := new([]string) // 設置一個指向類型為string的切片的指針

	var curr []byte
	backtrack(ans, curr, 0, 0, n)

	return *ans // 反取指針，獲得結果切片
}

// 回溯函數
func backtrack(ans *[]string, curr []byte, open int, close int, max int) {
	if len(curr) == max * 2 {
		*ans = append(*ans, string(curr[:]))
		return
	}

	if open < max { // 左括號沒有超過最大值，則添加做括號，最後刪除切片的最後一個元素
		curr = append(curr, '(')
		backtrack(ans, curr, open+1, close, max)
		curr = append(curr[0:len(curr)-1], curr[len(curr):]...) // 這個刪除方式最直接，但是
	}

	if close < open { // 當右括號比作括號少，則添加，最後刪除切片的最後一個元素
		curr = append(curr, ')')
		backtrack(ans, curr, open, close+1, max)
		curr = append(curr[0:len(curr)-1], curr[len(curr):]...)
	}
}

回溯也就是動態規劃，把每次結果都帶入到下一次回溯中，通過比較開閉括號的個數，來動態地調整。
算法題有時候可以考慮多種解法去實現，刷題的同時也能體會到不同編程語言的妙處。
本文首發自我的微信公眾號：成都有娃兒，歡迎關注。