LeetCode 22. Generate Parentheses

問題はこちら
難易度はmedium

問題概要

n組の括弧が与えられたとき、整った括弧の組合せをすべて生成する関数を書きなさい。

整う、とは左から読んでいく時に、左括弧 "(" が常に右括弧 ")" よりも多いか同じだけあることである。

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1
Output: ["()"]

答え

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def generate(p, left, right, parens=[]):
            if left:
                generate(p + '(', left-1, right)
            if right > left:
                generate(p + ')', left, right-1)
            if not right:
                parens += p,
            return parens
        
        return generate('', n, n)

generate()は再帰関数。leftとrightが０になるまで呼ばれる。
p: 答えとなる括弧の文字列の一つ。関数が呼ばれるたびに右か左の括弧をひとつ付け足す。
left: 使わなければならない残りの左括弧の数。
right: 残りの右括弧の数。関数が呼ばれるたびleftかrightのどちらかがひとつ減る。
parens: 最終的に答えとなる答えのリスト。leftとrightの両方が０になった時のpが追加される。

例えば括弧が２組の時、最初に引っかかるのはif leftだけなので

generate( '(', 1, 2 )

が呼ばれる。

generate( '(', 1, 2 )の次は if left と if right > left に引っかかるので

generate( '((', 0, 2 )
generate( '()', 1, 1 )

が呼ばれる。

コード改良

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def generate(p, left, right):
            if right == 0:
                yield p
                return

            if left > 0:
                yield from generate(p + '(', left - 1, right)

            if right > left:
                yield from generate(p + ')', left, right - 1)

        return list(generate('', n, n))

一応yieldも使える。意味はあるのだろうか？