Generate Parentheses

• LeetCode 사이트에서 친절한 풀이를 제공한다
• 내 경우는 사이트 해설의 3번 어프로치를, DP 스타일로 재귀 호출을 쓰지 않도록 살짝 변형해서 풀었다.
• 올바른 괄호를 모두 나열하는 것이 아니라, 갯수만 구하는 문제로는 괄호가 있다
  • 왜 이게 카탈랑 수가 되는지는 그 문제를 참고.
• 카탈랑 수의 일반항과 그 바운드를 계산하는 방법은 LeetCode의 풀이에서 생략되어 있는데, 그것에 관해서는 카탈랑 수 (Catalan number)를 참고.

"""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]