22. Generate Parentheses

题目：

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1
Output: ["()"]

Constraints:

• 1 <= n <= 8

思路1：

题意大致是给定一个整数n，返回所有有效的的拥有n对括号的string。首先成立的string一定是2 * n长度，即n个左括号和n个右括号构成，另外再证明有效性即可。因为数据量只到8，所以暴力搜索是可以过的。回溯的base case是string长度到达2 * n并且能够被证明有效性。

代码1：

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<int> rest = { n, n };
        backtracking(s, 0, rest, n);
        return res;
    }
private:
    vector<string> res;
    string s;
    bool check(string& s) {
        stack<char> st;
        for (auto c : s) {
            if (c == ')') {
                if (st.size() && st.top() == '(')
                    st.pop();
                else
                    return false;
            }
            else
                st.push(c);
        }
        return st.empty();
    }
    void backtracking(string &s, int cur, vector<int>& rest, int n) {
        if (s.size() == 2 * n) {
            if (check(s))
                res.push_back(s);
            return;
        }
        for (int i = cur; i < 2 * n; i++) {
            if (rest[0] > 0) {
                s.push_back('(');
                 rest[0]--;
                backtracking(s, i + 1, rest, n);
                s.pop_back();
                rest[0]++;
            } 
            if (rest[1] > 0) {
                s.push_back(')');
                rest[1]--;
                backtracking(s, i + 1, rest, n);
                s.pop_back();
                rest[1]++;
            }
        }
    }
};

思路2：

我们也可以在保证有效性的情况下添加括号，分为两种条件1)如果左括号还能添加，即当前string中左括号的数量小于n，那么可以无脑添加，不会影响有效性；2)如果string中右括号比左括号少，则也可以添加右括号。这样在base case跳出的时候就不用额外判断是否有效了，直接把当前string添加到集合即可。

代码2：

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        backtracking(s, 0, 0, n);
        return res;
    }
private:
    vector<string> res;
    string s;
    void backtracking(string &s, int left, int right, int n) {
        if (s.size() == 2 * n) {
            res.push_back(s);
            return;
        }
        if (left < n) {
            s.push_back('(');
            backtracking(s, left + 1, right, n);
            s.pop_back();
        }
        if (right < left) {
            s.push_back(')');
            backtracking(s, left, right + 1, n);
            s.pop_back();
        }
    }
};