Problem
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Examples:
Input: n=3
Output:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
Solutions
- 可以暴力求解, 將所有括號的全排列找出來,然后把里面括號匹配的拿出來
- 動態(tài)規(guī)劃, 第n個括號總是在第n-1個括號的基礎(chǔ)上添加的,假設最左邊的左括號是添加上去的. 那么, 前面的n-1個括號便分為兩部分,在新加入括號內(nèi)部的, 和不在新括號內(nèi)部的. 我們遍歷在括號內(nèi)部的括號對數(shù)0-idx-1,然后遍歷在括號內(nèi)的每個排列, 以及不在括號內(nèi)的每個排列, 將他們拼湊到一起
C++ Codes
四層循環(huán), 第一層求2-n的結(jié)果, 第二層遍歷在新括號內(nèi)部的括號對數(shù), 第三層和第四層, 遍歷在新括號內(nèi)部的括號排列, 和不在括號內(nèi)部的括號排列, 加起來就是一個新的排列
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<vector<string> > dp(n+1);
dp[0]={""};
dp[1]={"()"};
//假設最左邊的左括號是第n對括號新加進來的
//遍歷在第一個左括號對應的括號內(nèi)的pair數(shù), [0, idx-1]
for(int idx=2;idx<=n;idx++)
for(int i=0;i<=idx-1;i++) //在第一個左括號內(nèi)的括號數(shù)
for(string si:dp[i]) //在第一個括號內(nèi)的括號數(shù)的每個排列
for(string sk:dp[idx-1-i]) //不在第一個括號內(nèi)的括號的每個排列
dp[idx].push_back("("+si+")"+sk);
return dp[n];
}
};
Python Codes
算法同C++
class Solutin:
def generateParenthesis(self, n: int) -> List[str]:
if n == 0:
return []
total_l = []
total_l.append([None])
total_l.append(["()"])
for i in range(2,n+1): # 開始計算i時的括號組合，記為l
l = []
for j in range(i): #遍歷所有可能的括號內(nèi)外組合
now_list1 = total_l[j]
now_list2 = total_l[i-1-j]
for k1 in now_list1: #開始具體取內(nèi)外組合的實例
for k2 in now_list2:
if k1 == None:
k1 = ""
if k2 == None:
k2 = ""
el = "(" + k1 + ")" + k2
l.append(el)
total_l.append(l)
return total_l[n]
總結(jié)
- 動態(tài)規(guī)劃往往是遞歸轉(zhuǎn)化過來, 如果能想到遞歸, 那可以考慮下DP怎么做, 當然, 暴力求解通常就是遞歸求解
