Description

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

Solution

給定整數(shù)n蔚晨，產(chǎn)生n對括號構成的配對字符串，常規(guī)的排列組合問題肛循，遞歸和迭代兩類解法，medium

• 遞歸法
  left和right表示還剩多少'('银择、')'可以放置多糠，因此對于'('，只要left>0即可以向下層調(diào)用浩考，而對于')'必須保證right>left夹孔，否則無法完成配對

vector<string> generateParenthesis(int n) {
    vector<string> ret;
    this->dfsGenerateParenthesis(ret, "", n, n);
    return ret;
}
void dfsGenerateParenthesis(vector<string>& ret, string s, int left, int right) {
    if (left ==0 && right == 0) {
        ret.push_back(s);
        return ;
    }
    if (left > 0) {
        this->dfsGenerateParenthesis(ret, s + '(', left - 1, right);
    }
    if (right > left) {
        this->dfsGenerateParenthesis(ret, s + ')', left, right - 1);
    }
}

• 迭代法
  循環(huán)遍歷，層次交換，每一輪的結果是在上一輪結果的基礎上進行加工生成的搭伤，并且中間結果還需要攜帶left只怎、right的字段信息，因此定義了新的struct

struct MyNode {
    int left;
    int right;
    string path;
    MyNode(int x, int y, string s) : left(x), right(y), path(s) {}
};
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        MyNode node(n, n, "");
        vector<MyNode> retInfo(1, node);
        vector<string> ret;
        for (int i = 0; i < 2 * n; ++i) { //一共要放置2*n個字符
            vector<MyNode> curRetInfo;
            for (int j = 0; j < retInfo.size(); ++j) {
                int left = retInfo[j].left, right = retInfo[j].right;
                string s = retInfo[j].path;
                if (left > 0) {
                    MyNode node(left - 1, right, s + '(');
                    curRetInfo.push_back(node);
                }
                if (right > left) {
                    MyNode node(left, right - 1, s + ')');
                    curRetInfo.push_back(node);
                }
            }
            retInfo = curRetInfo;
        }
        for (int k = 0; k < retInfo.size(); ++k) {
            ret.push_back(retInfo[k].path);
        }
        return ret;
    }
};