LeetCode Generate Parentheses 深度分析了解

Generate Parentheses 

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

原創位址：http://blog.csdn.net/kenden23/article/details/16951299

此題給人一看就是眼花缭亂的感覺。在紛繁的特征中總結出來規律還真是非常難的。

網上分析實在太少了，令人難以看明白。

是以我在這裡分析一下，覺得我分析得不好，或者深度不夠的，請多多指教。

以我的思維，我是使用二叉樹的思維思考這個算法的，不過最後沒能自己成功的寫出程式。查了查LeetCode論壇，使用的是遞歸算法，感覺真是精妙絕倫！因為我考慮這個遞歸樹的時候有兩個難點：

1 如何兩邊同時周遊一棵樹？

2 如何剔除不适合的路徑？比如最中間的路徑是不滿足條件的。

到底是什麼樣的樹？構造出這樣的概念樹，我覺得就好了解很多了。

看看下面我畫的樹：

順着路徑對稱地，比如最左邊和最右邊，周遊兩個路徑，就是一個解，除了最中間的不符合要求。是以要周遊這樣的概念樹，很困難。

下面是程式出處：http://discuss.leetcode.com/questions/203/generate-parentheses

vector<string> generateParenthesis(int n) {
    vector<string> ans;
    if (n>0) generator(ans, "", 0, 0, n);
    return ans;
}

void generator(vector<string> & ans, string s, int l, int r, int n) { // r/l: appearance of ) (
    if (l == n) {
        ans.push_back(s.append(n-r, ')'));
        return;
    }
    generator(ans, s+'(', l+1, r, n);
    if (l>r) generator(ans, s+")", l, r+1, n);
}
           

逐句看看吧，反正沒多少。

if (l == n) {
        ans.push_back(s.append(n-r, ')'));
        return;
    }
           

這個功能是已經周遊了左邊的樹，然後這裡并不需要周遊右邊的樹，而是非常巧妙地直接補上右括号“）”就完事了。沒做過的話，真是想破頭腦都難想出來。

而這樣居然神奇地完成一個解了。

generator(ans, s+'(', l+1, r, n);
           

這句就是周遊左遞歸樹，是先序周遊哦，有人說了解為後序，不對，應該是先序。因為s+'('就是先把"("加進去了，然後到下一層樹節點。

左子樹遞歸周遊完了就開始右子樹遞歸周遊：

if (l>r) generator(ans, s+")", l, r+1, n);
           

右子樹都是“）”右括号的，是以s+")"代表周遊右子樹。

不過令人頭痛的就是怎麼了解if(l>r)這個條件？

看了些部落格說了解為不能讓右括号多于左括号，有一定道理，那為什麼前面周遊左子樹的時候，就是填寫左括号“（”的時候，不添加一個判斷左子樹不能大于右子樹的條件呢？是以這樣了解好像不大合理。

我的了解，這句正是剔除中間不符合條件的路徑的巧妙句子。

因為隻有左子樹的最右邊的子樹才會可能出現右括号")"大于左括号"("的情況的，是以這個條件真是"黃娟! 幼婦! 外孫"！

2014-1-25 update

 遞歸回溯法的程式，其實題目并不難，上面的分析我重新看看，使用樹的思維分析也可以，不過如果熟悉了，那麼還是不需要分析的太麻煩，不過這樣分析對思維鍛煉很有好處。

本題最難的就是一個條件判斷啦，如我重新寫了個程式，如下。這個條件就是if （left < right），這是個十分難想出來的條件，最後怎麼吃透這個條件呢？

我就是使用執行個體，反複走幾遍，然後就确立了這個條件，這就是根據執行個體觀察其中的規律的能力了。

雖然就是那麼一個條件，自己摸索出來，難度還是相當大的。是以本題我覺得因人而異才能确定其難度指數，我覺得相對難度應該達到4.5星級了，不注意的話，面試的時候是很難寫出正确的程式的。也許寫個差不多的程式是可以的，不過所謂的差不多程式，就是差一點點沒正确的程式，說到底就是錯誤的程式。

class Solution {
public:
    vector<string> generateParenthesis(int n) 
	{
		vector<string> rs;
		string s;
		genParenthesis(rs, s, n, n);
		return rs;
	}
	void genParenthesis(vector<string> &rs, string &s, int left, int right)
	{
		if (left==0)
		{
			rs.push_back(s);
			rs.back().append(right, ')');
			return;
		}

		s.push_back('(');
		genParenthesis(rs, s, left-1, right);
		s.pop_back();
		if (left < right)
		{
			s.push_back(')');
			genParenthesis(rs, s, left, right-1);
			s.pop_back();
		}
	}
};
           

 難度指數： 4.5星級