Leetcode-22Generate Parentheses

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:

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

题解：

输入 n 表示有 n 组括号，输出这 n 组括号中所有合法的括号；
例如：
三组括号中的合法括号有：
"((()))", "(()())", "(())()", "()(())", "()()()"；

分析：

首先，我们先不考虑括号合法的问题，先输出这 n 组括号中所有括号的组合：
可以用递归的方式，两个递归，item + ‘(’ 和 一个item + ‘)’ ；

image.png

接下来，我们来观察合法括号的规律，可以发现：合法括号中如果 "()" 算配对成功，予以抵消的话，左括号永远要先于右括号；
我们定义一个 sum = 0，每添加一个左括号 sum + 1；每添加一个右括号 sum - 1；
在添加括号的过程中：

1. 如果 sum < 0：说明除去配对成功的括号以后右括号出现在了左括号前面；非法，不再继续添加括号，剪枝；
2. 如果 sum > n：说明添加的左括号已经超过了总数量的一半，不可能全部配对；非法，不再继续添加括号，剪枝；
3. 如果添加的括号数达到n组的数量时，sum == 0：说明当前的括号全部配对成功，合法，将结果存入 result；

My Solution（C/C++完整实现）：

#include <cstdio>
#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        add_item(0, n, "", 0, result);
        return result;
    }
private:
    void add_item(int i, int n, string item, int sum, vector<string> &result) {
        //if (sum > 3 || sum < 0) {
        //  return;
        //}
        if (i == 2 * n) {
            if (sum == 0) {
                result.push_back(item);
            }
            return;
        }
        if (sum > 3 || sum < 0) {
            return;
        }
        add_item(i + 1, n, item + "(", sum + 1, result);
        add_item(i + 1, n, item + ")", sum - 1, result);
    }
};

int main() {
    vector<string> result;
    Solution s;
    result = s.generateParenthesis(3);
    for (int i = 0; i < result.size(); i++) {
        cout << result[i] << endl;
    }
    return 0;
}

结果：

((()))
(()())
(())()
()(())
()()()

My Solution:

class Solution:
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        result = []
        self.formed_p(n, '', 0, 0, result)
        return result

    def formed_p(self, n, item, left, right, result):
        if len(item) == 2 * n:
            result.append(item)
            return
        if left < n:
            self.formed_p(n, item + '(', left + 1, right, result)
        if right < left:
            self.formed_p(n, item + ')', left, right + 1, result)