22. Generate Parentheses

• 方法1: backtracking
• • 易错点
  • 易错点

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:

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

方法1: backtracking

思路：

用递归来生成下一个字符，那么我们需要排除一些不合法的顺序。我们用left和right来传递可用的左右括号数量。如果left > right 说明递归进来的字符串有先于左括号出现的右括号，不予以处理直接返回。如果left <= right，但是left = right = 0，此时已经产生一个合理解，需要推入结果。否则left剩下可以推left，right剩下可以推right，将相应的可用数量-1。

易错点

1. 这里传递tmp的时候不能是&，因为tmp + “(” is not lvalue。那么要么选择pass by value，要么再push/pop操作tmp

class Solution1 {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        string tmp = "";
        generateHelper(result, tmp, n, n);
        return result;
    }
    void generateHelper(vector<string> & result, string tmp, int left, int right){
        if (left > right){
            return;
        }
        if (left == 0 && right == 0){
            result.push_back(tmp);
        }
        if (left > 0){
            generateHelper(result, tmp + "(", left - 1, right);
        }
        if (right > 0){
            generateHelper(result, tmp + ")", left, right - 1);
        }
        return;
    }
};
           

另一种写法，判断的条件也稍微发生改变：如果left < n就可以继续放入左括号，但是右括号必须满足right > left 才允许进行推入（可以加快不少），并且用push/pop来操作tmp。

易错点

1. right > left 而不是right >= left

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        string tmp = "";
        generateHelper(result, tmp, n, n);
        return result;
    }
    void generateHelper(vector<string> & result, string & tmp, int left, int right){
        if (left == 0 && right == 0){
            result.push_back(tmp);
        }
        if (left > 0){
            tmp.push_back('(');
            generateHelper(result, tmp, left - 1, right);
            tmp.pop_back();
        }
        if (right > left){
            tmp.push_back(')');
            generateHelper(result, tmp, left, right - 1);
            tmp.pop_back();
        }
        return;
    }
};