1.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:
[ "((()))", "(()())", "(())()", "()(())", "()()()"]

題目思路:
 》尬!①不難發(fā)現(xiàn),n為0的時候輸出是空,而n = 1的時候主经,輸出“()”
  ②當n > 1的時候庭惜,要使得整個括號字符串可以配對罩驻,那么與第一個配對的右括號把n - 1對括號分成了一個 i (0 <= i < n)對已配對的括號和 n - 1 - i對已配對的括號。那么把所有的右括號劃分的情況全部列出來就可以了护赊。由于這里的時間復雜度比較復雜惠遏,就不作分析了砾跃。
根據(jù)上述可以得到:
f(n) = ∑( '(' + f(i) +')' + f(n - 1 - i) )

class Solution(object):
    """
      :type n: int
      :rtype: List[str]
      """
    def generateParenthesis(self, n):
        result = []
        def func(left,right,s):
            if  left < right :
                return
            if (left+right == n*2):
                if (left == right):
                    result.append(s)
                return
            func(left,right+1,s+')')
            func(left+1,right,s+'(')
        func(1,0,'(')
        return  result

遞歸解法,左括號的個數(shù)比右括號多

class Solution(object):
    """
      :type n: int
      :rtype: List[str]
      """
    def generateParenthesis(self, n):
        result = []
        def func(left,right,s):
            if  left < right :
                return
            if (left+right == n*2):
                if (left == right):
                    result.append(s)
                return
            func(left,right+1,s+')')
            func(left+1,right,s+'(')
        func(1,0,'(')
        return  result
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市节吮,隨后出現(xiàn)的幾起案子抽高,更是在濱河造成了極大的恐慌,老刑警劉巖透绩,帶你破解...
    沈念sama閱讀 222,681評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件翘骂,死亡現(xiàn)場離奇詭異,居然都是意外死亡渺贤,警方通過查閱死者的電腦和手機雏胃,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評論 3 399
  • 文/潘曉璐 我一進店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來志鞍,“玉大人,你說我怎么就攤上這事方仿」膛铮” “怎么了?”我有些...
    開封第一講書人閱讀 169,421評論 0 362
  • 文/不壞的土叔 我叫張陵仙蚜,是天一觀的道長此洲。 經(jīng)常有香客問我,道長委粉,這世上最難降的妖魔是什么呜师? 我笑而不...
    開封第一講書人閱讀 60,114評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮贾节,結(jié)果婚禮上汁汗,老公的妹妹穿的比我還像新娘。我一直安慰自己栗涂,他們只是感情好知牌,可當我...
    茶點故事閱讀 69,116評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著斤程,像睡著了一般角寸。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上忿墅,一...
    開封第一講書人閱讀 52,713評論 1 312
  • 那天扁藕,我揣著相機與錄音,去河邊找鬼疚脐。 笑死亿柑,一個胖子當著我的面吹牛,可吹牛的內(nèi)容都是我干的亮曹。 我是一名探鬼主播橄杨,決...
    沈念sama閱讀 41,170評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼秘症,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了式矫?” 一聲冷哼從身側(cè)響起乡摹,我...
    開封第一講書人閱讀 40,116評論 0 277
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎采转,沒想到半個月后聪廉,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,651評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡故慈,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,714評論 3 342
  • 正文 我和宋清朗相戀三年板熊,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片察绷。...
    茶點故事閱讀 40,865評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡干签,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出拆撼,到底是詐尸還是另有隱情容劳,我是刑警寧澤,帶...
    沈念sama閱讀 36,527評論 5 351
  • 正文 年R本政府宣布闸度,位于F島的核電站竭贩,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏莺禁。R本人自食惡果不足惜留量,卻給世界環(huán)境...
    茶點故事閱讀 42,211評論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望哟冬。 院中可真熱鬧楼熄,春花似錦、人聲如沸柒傻。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,699評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽红符。三九已至青柄,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間预侯,已是汗流浹背致开。 一陣腳步聲響...
    開封第一講書人閱讀 33,814評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留萎馅,地道東北人双戳。 一個月前我還...
    沈念sama閱讀 49,299評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像糜芳,于是被迫代替她去往敵國和親飒货。 傳聞我的和親對象是個殘疾皇子魄衅,可洞房花燭夜當晚...
    茶點故事閱讀 45,870評論 2 361

推薦閱讀更多精彩內(nèi)容

  • 背景 一年多以前我在知乎上答了有關(guān)LeetCode的問題, 分享了一些自己做題目的經(jīng)驗。 張土汪:刷leetcod...
    土汪閱讀 12,748評論 0 33
  • 個人學習批處理的初衷來源于實際工作塘辅;在某個迭代版本有個BS(安卓手游模擬器)大需求晃虫,從而在測試過程中就重復涉及到...
    Luckykailiu閱讀 4,733評論 0 11
  • HProf 在 Android Studio 中的展示詳解,基于我對其的理解扣墩,我將其根據(jù) heap,count,s...
    仰簡閱讀 2,538評論 0 3
  • 我們每個人總有一份貪心哲银,選擇了其一,總想著擁有其二呻惕。正如張愛玲所描述的一樣荆责,擁有了紅蘋果,總會認為那個青蘋果更加可...
    莜薇閱讀 196評論 0 1
  • 在知乎上有一個“天涯社區(qū)能否翻盤,延續(xù)傳奇濒持?”的問題山憨,下面有個有意思的回答: 我就說一句話:就連我們水軍都開始轉(zhuǎn)移...
    奔雷閱讀 5,745評論 0 1