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:

"((()))", "(()())", "(())()", "()(())", "()()()"

解题方法

一开始没有什么头绪，但是做到一道也是parentheses的题目，是valid parentheses,是将(存在stack来解决。 大概想到的思路是在从开头开始的string里，(的数量都应该比)的数量多，而且可以一直加入(。所以如果我们 从左往右构建的话，就应该遵循这种规则，直到用完所有的pair.

pair的数量为n，那么从左往右的过程中，只有两种选择，(或者), 加入哪种的选择规则是

• 如果(的数量小于n,就还可以加入(
• 如果(的数量大于), 就可以加入)

而为了产生所有的组合，而且这是有顺序的，就应该像subsets那样用dfs的方法做

Solution

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        if not n:
            return []

        results = []
        self.helper(n, results, 0, 0, [])
        return results

    def helper(self, n, results, leftP, rightP, curList):
        if len(curList) == n * 2:
            newStr = "".join(curList)
            results.append(newStr)

        if leftP < n:
            curList.append('(')
            self.helper(n, results, leftP+1, rightP, curList)
            curList.pop()

        if leftP > rightP:
            curList.append(')')
            self.helper(n, results, leftP, rightP + 1, curList)
            curList.pop()

Reference

• generate parentheses