22. Generate Parentheses

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

给定整数n，产生n对括号构成的配对字符串，常规的排列组合问题，递归和迭代两类解法，medium

• 递归法
  left和right表示还剩多少'('、')'可以放置，因此对于'('，只要left>0即可以向下层调用，而对于')'必须保证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);
    }
}

• 迭代法
  循环遍历，层次交换，每一轮的结果是在上一轮结果的基础上进行加工生成的，并且中间结果还需要携带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;
    }
};