[leetcode] 22. 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:

[ "((()))", "(()())", "(())()", "()(())", "()()()" ]

 

풀이

분할정복법으로 풀이가 가능하다.

임의의 괄호열은 "( 괄호열1 ) 괄호열2" 꼴로 나타낼 수 있다.

또한 괄호열1과 괄호열2를 만드는 것은 전체문제의 subproblem이기 때문에 분할정복법이 가능한 것이다.

 

괄호열1이 $i$쌍의 괄호열이라면 총 $n$쌍이기 때문에, 괄호열2는 $n-1-i$쌍이 된다.

또한, 임의의 괄호열에 대해서 i값은 유일하게 정해진다.

따라서, 0부터 n-1까지의 i에 대해서, generateParenthsis(i)와 generateParenthesis(n-1-i)를 구한다.

각각 구한 쌍에 대해서, 모든 "( 괄호열1 ) 괄호열2"의 조합을 만들면 된다.

 

정답을 모두 구해야하기 때문에 시간복잡도는 정답 개수에 binding 된다.

괄호열의 개수는 n번째 카탈란 수라는 것이 알려져 있다.

 

Time Complexity : $O( |ans| )$

 

코드

class Solution {
private:
    string lp = "(";
    string rp = ")";
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        if(n==0) ans.push_back("");
        else for(int i=0;i<n;i++)
            for(string l: generateParenthesis(i))
                for(string r:generateParenthesis(n-1-i))
                    ans.push_back(lp+l+rp+r);
        return ans;
    }
};