# LeetCode Medium 22. Generate Parentheses
tags: leetcode
問題
$n$組のかっこが与えられた時に, 全ての適切なかっこの組み合わせを全て生成する関数を作れ
解法(recursive)
左右のかっこの個数がそれぞれ$n$個である文字列を生成するという問題です
下のように空の文字列に(
と)
を繋げて文字列を作ります
このとき, 左右かっこを繋げる動作を再帰的に定義できます
- ここでは左のかっこの数と右のかっこの数をそれぞれ
lnum
,rnum
とします lnum
の左かっことrnum
の右かっこからできる文字列をcur_str
とします- 基底は
cur_str
の長さが入力の$n$の2倍になったとき(lnum
とrnum
がそれぞれ$n$個のとき)です
- 基底は
- では基底に合わせて左右かっこの数が揃うように文字列を生成すれば良いです
- 上の図を見ると右のかっこは左のかっこより少ない時に文字列に連結されます
- 左のかっこは$n$まで連結します
以上から下のようにコードを書くことが可能です
Python
class Solution: def generateParenthesis(self, n: int) -> List[str]: ans = [] def helper(lnum = 0, rnum = 0, cur_str = ""): if len(cur_str) == 2 * n: ans.append(cur_str) return if lnum < n: helper(lnum + 1, rnum, cur_str + '(') if rnum < lnum: helper(lnum, rnum + 1, cur_str + ')') helper() return ans
C++
class Solution { public: vector<string> generateParenthesis(int n) { vector<string> ans; helper(n, 0, 0, "", ans); return ans; } private: void helper(int maxn, int lnum, int rnum, string cur_str, vector<string>& ans) { if (cur_str.size() == 2 * maxn) { ans.push_back(cur_str); return; } if (lnum < maxn) { helper(maxn, lnum+1, rnum, cur_str + "(", ans); } if (rnum < lnum) { helper(maxn, lnum, rnum+1, cur_str + ")", ans); } } };