LeetCode-algorithms 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对括号匹配的所有情况，解题思路为1、一对括号总是左括号先出现，不可能有多出来的单独的右括号。2、左括号和右括号的个数总是匹配的。
    无论上一个字符是什么，接下来的字符都有可能是“（”和“）”两种情况，因此整个问题实际上是一个二叉树，根节点为“（”，接下来有“（（”和“（）”两个子节点，如此类推，只要把符合要求的节点记录下来，不符合的去掉则可，因为是N对括号，因此树的深度为2*n。
    对于这样的2叉树我选择了用递归来处理，添加一些约束条件会使得不用完全生成整棵树。由于字符比较难处理，因此我选择使用1代表左括号，-1代表右括号。所以当1、整个list的和小于0时不在往下递归。2、list和为0且list个数为2*n则符合条件。
    最后把得出的结果转换成字符串即可得到答案。
代码：
class Solution(object):    def changeToParentheses(self,ans):    	result = []    	for a in ans:    		string = ""    		for num in a:    			if num == 1:    				string+="("    			else:    				string+=")"    		result.append(string)    	return result    	    def test(self,ans,list_,num,n):        import copy    	list_.append(num)    	if len(list_) == n*2 and sum(list_) == 0:    		ans.append(list_)    	elif len(list_) < n*2 and sum(list_) >= 0:    		self.test(ans,copy.copy(list_),1,n)    		self.test(ans,copy.copy(list_),-1,n)     		    def generateParenthesis(self, n):        """        :type n: int        :rtype: List[str]        """        ans = []        self.test(ans,[],1,n)        return self.changeToParentheses(ans)