leecode题解22- 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:

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

思路： 回溯法

The idea here is to only add ‘(’ and ‘)’ that we know will guarantee us a solution (instead of adding 1 too many close). Once we add a ‘(’ we will then discard it and try a ‘)’ which can only close a valid ‘(’. Each of these steps are recursively called.

代码1：反向

class Solution {
public:
    // 回溯法
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        backTracking(result, "", n, n);   
        return result;
    }
    // slt 目标vector； str 当前字符串； left 待插入左括号个数； right 待插入右括号个数
    void backTracking(vector<string> &rlt, string str, int left, int right){
        // 若没有待插入的左右括号时，满足条件
        if(left==0 && right==0){
            rlt.push_back(str);
            return;
        }
        //如果还有待插入的左括号，插入左括号
        if(left > 0) backTracking(rlt, str+"(", left-1, right);
        // 如果 待插入的右括号个数 多于 待插入的左括号个数，则插入右括号
        if(right > left) backTracking(rlt, str+")", left, right-1);
    }
};
           

代码2：正向

class Solution {
public:
    // 回溯法
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        backTracking(result, "", 0, 0, n);   
        return result;
    }
    // slt 目标vector； str 当前字符串； left 当前字符串左括号个数； right 当前字符串右括号个数； max 最大单向括号个数
    void backTracking(vector<string> &rlt, string str, int left, int right, int max){
        // 若当前字符串长度等于 max*2， 满足条件
        if(str.length() == max*2){
            rlt.push_back(str);
            return;
        }
        //如果左括号还没有插入max个，则插入左括号
        if(left < max) backTracking(rlt, str+"(", left+1, right, max);
        // 如果当前右括号个数小于当前左括号个数，则可以插入右括号
        if(right < left) backTracking(rlt, str+")", left, right+1, max);
    }
};