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;
    }
};