====== Generate Parentheses ======

===== 풀이 =====
  * LeetCode 사이트에서 [[https://leetcode.com/problems/generate-parentheses/solution/|친절한 풀이]]를 제공한다
  * 내 경우는 사이트 해설의 3번 어프로치를, DP 스타일로 재귀 호출을 쓰지 않도록 살짝 변형해서 풀었다.
  * 올바른 괄호를 모두 나열하는 것이 아니라, 갯수만 구하는 문제로는 [[ps:problems:boj:10422|괄호]]가 있다
    * 왜 이게 카탈랑 수가 되는지는 그 문제를 참고. 
  * 카탈랑 수의 일반항과 그 바운드를 계산하는 방법은 LeetCode의 풀이에서 생략되어 있는데, 그것에 관해서는 [[ps:카탈랑 수]]를 참고.

===== 코드 =====
<dkpr py>
"""Solution code for "LeetCode 22. Generate Parentheses".

- Problem link: https://leetcode.com/problems/generate-parentheses/
- Solution link: http://www.teferi.net/ps/problems/leetcode/22
"""


class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        par_lists = [[] for _ in range(n + 1)]
        par_lists[0] = ['']
        for i in range(1, n + 1):
            for j in range(i):
                left_list = par_lists[j]
                right_list = par_lists[i - j - 1]
                for l in left_list:
                    par = '(' + l + ')'
                    par_lists[i].extend([par + r for r in right_list])

        return par_lists[n]

</dkpr>