括号生成

问题描述

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
例如，给出 n = 3，生成结果为：

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

思路

本题用了回溯算法来生成括号组合。

在最开始需要注意的地方是，n是括号的对数，所以递归的步数应该是n=n*2。
每次递归的选择只有‘（’和“）”两种选择。
当递归的次数到达n时在返回上一层递归时，要先判断是不是有效的括号组合，如果是有效的括号组合，则将括号组合插入到返回结果vector<int> A中。
返回上一层递归后，删除字符串的最一个字符用 str.substr(0, str.length() - 1)

判断字符是否为有效括号组合：

如果字符为“（”，那么将其push到栈中，如果为“）”那么在栈中弹出一个“）”。
当栈为空的时候弹出“）”则直接可以判断不是一个有效的括号组合。
到最后的时候栈不为空，则说明“（”比较多，也说明不是有效的括号组合。

题解

class Solution {
public:
    vector<string> A;

    vector<string> generateParenthesis(int n) {
        n = n * 2;
        dfs(n, 0, A);
        return A;
    }

    string str;

    void dfs(int n, int step, vector<string> &A) {

        if (step == n) {
            if (alter(str) == 0) {
                A.push_back(str);
            }
            return;
        }
        for (int i = 0; i < 2; i++) {
            if (i == 0) {
                str = str + "(";
            } else {
                str += ")";
            }
            dfs(n, step + 1, A);
            str = str.substr(0, str.length() - 1);
        }
    }

    int alter(string string1) {
        stack<string> stack1;
        int n = string1.length();
        for (int i = 0; i < n; i++) {
            if (string1[i] == '(') {
                stack1.push("(");
            } else if (string1[i] == ')') {
                if (!stack1.empty()) { stack1.pop(); }
                else {return -1;}
            }
        }
        if (stack1.empty()) {
            return 0;
        } else {
            return -1;
        }
    }
};