#!/usr/bin/python
#-*- coding:utf-8 -*-

"""
   由于这题和检查有效括号字符串那题属于一个上下文，一些面试者会想到一个清奇的思路，就是先生成
   全部的排列然后再排除无效的。这种思路就不赘述了，肯定会被判定为不优的。

   正确的思路应该就是递归（recursion）。简单思路就是如果有n对括号，那么每个字符串就一定有2n个字符，
   每生成一个字符实际上都在做一个二分决策，即“我是接下来生成开阔号'('好呢，还是闭括号')'好呢？“
   如果决策正确，我们将最终得到一个有效的括号字符串，便可将其加入solution_set当中去。

   从二叉树的角度可以可视化这个过程(n=2为例)：
                       ''
                       / 
                    '('     
                   /    \    
                 '()'   '(('
                 /         \
               '()('       '(()'
               /             \
           '()()'           '(())'

   虽然我们最终只取二叉树的叶子节点，但是实际上我们还是遍历了途径节点，所以算法时间复杂度是O（2^n)。

   如果被要求写循环（iteration）的方式做的话，借助一个有Stack（栈）功能的数据结构就能搞定了。

   任何recursion能解决的问题都是借助了函数本身call stack的特性，都可以想到在转循环写法的时候用到栈。
"""

def generate_parentheses(n):
   solution_set = []
   # 基础参数：空结果集，空字符串，已添加0个开括号，已添加0个闭括号，需要填充n对括号
   generate_parentheses_recursive(solution_set, "", 0, 0, n)
   return solution_set

def generate_parentheses_recursive(solution_set, current, num_open, num_close, n):
   # 当已添加开括号和已添加闭括号都达到n时：
   if (num_open == n and num_close == n):
       # 得到了一个有效的括号字符串，将其加入结果集
       solution_set.append(current)
   # 当开括号还不够时：
   if num_open < n:
       # 继续添加开括号
       generate_parentheses_recursive(solution_set, current+"(", num_open+1, num_close, n)
   # 当开括号已满，但闭括号还不够时：
   if num_open > num_close:
       #继续添加闭括号
       generate_parentheses_recursive(solution_set, current+")", num_open, num_close+1, n)

def generate_parentheses_iterative(n):
   solution_set = []
   s = []
   s.append(("", 0, 0, n))
   while (len(s) != 0):
       top = s.pop()
       if (top[1] == n and top[2] == n):
           solution_set.append(top[0])
       if top[1] < n:
           s.append((top[0]+"(", top[1]+1, top[2], n))
       if top[1] > top[2]:
           s.append((top[0]+")", top[1], top[2]+1, n))
   return solution_set

if __name__ == "__main__":
   print(generate_parentheses(3))
   print(generate_parentheses_iterative(3))```