Tuesday, November 18, 2014

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

思路:

通过向string插入"("和")"直到两者的数量都为n,则一个combination构建完成。如何保证这个combination是well-formed?在插入过程中的任何时候:

1. 只要"("的数量没有超过n,都可以插入"("。
2. 而可以插入")"的前提则是当前的"("数量必须要多余当前的")"数量。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> allComb;
        string comb;
        findParenthesis(n, 0, 0, comb, allComb);
        return allComb;
    }
    
    void findParenthesis(int n, int nleft, int nright, string &comb, vector<string> &allComb) {
        if(nleft==n && nright==n) {
            allComb.push_back(comb);
            return;
        }
        
        if(nleft<n) {
            comb.push_back('(');
            findParenthesis(n, nleft+1, nright, comb, allComb);
            comb.pop_back();
        }
        
        if(nright<nleft) {
            comb.push_back(')');
            findParenthesis(n, nleft, nright+1, comb, allComb);
            comb.pop_back();
        }
    }
};

No comments:

Post a Comment