akmhmgc · akmhmgc · Oct 7, 2025 · nodchip · Oct 8, 2025 · akmhmgc
diff --git a/22/step1.md b/22/step1.md
@@ -0,0 +1,65 @@
+# step1 何も見ずに解く
+
+backtracking を使う。
+
+- `(`の数が n 個より少なければ`(`を 1 つつなげる
+- `)`の数が`(`より少なければ`)`を 1 つつなげる
+
+というパターンで分類。`)`の数が n と一致した時に parenthesis が完成するので答えに含める。
+
+```ruby
+# @param {Integer} n
+# @return {String[]}
+def generate_parenthesis(n)
+    combinations = []
+    generate_parenthesis_helper = lambda do |parenthesis, left ,right|
+        if right == n
+            combinations << parenthesis.join
+            return
+        end
+        if left < n
+            parenthesis << "("
+            generate_parenthesis_helper.call(parenthesis, left + 1, right)
+            parenthesis.pop
+        end
+        if right < left
+            parenthesis << ")"
+            generate_parenthesis_helper.call(parenthesis, left, right + 1)
+            parenthesis.pop
+        end
+    end
+    generate_parenthesis_helper.call([], 0, 0)
+    combinations
+end
+```
+
+他には、
+可能なだけ左を入れる + 右を一つ入れる
+という分類もできる。
+
+```ruby
+# @param {Integer} n
+# @return {String[]}
+def generate_parenthesis(n)
+    combinations = []
+    generate_parenthesis = lambda do |parenthesis, left ,right|
+        if right == n
+            combinations << parenthesis.join
+            return
+        end
+        (1..(n - left)).each do |i|
+            i.times { parenthesis << "(" }
+            parenthesis << ")"
+            generate_parenthesis.call(parenthesis, left + i, right + 1)
+            (i + 1).times { parenthesis.pop }
+        end
+        if left > right
+            parenthesis << ")"
+            generate_parenthesis.call(parenthesis, left, right + 1)
+            parenthesis.pop
+        end
+    end
+    generate_parenthesis.call([], 0, 0)
+    combinations
+end
+```
diff --git a/22/step2.md b/22/step2.md
@@ -0,0 +1,30 @@
+# step2 他の方の解答を見る
+https://github.com/olsen-blue/Arai60/pull/54/files/a0087de7fa136c0c271a07ec29a364c67f40d849#r2022389382
+
+> はじめの括弧とそれに対応する括弧に注目して「(A)B」と分けるのも分類ですね。
+
+この考え方は全く頭になかった。
+
+```ruby
+# @param {Integer} n
+# @return {String[]}
+def generate_parenthesis(n)
+    return [""] if n == 0
+
+    combinations = []
+    n.times do |i|
+        lefts = generate_parenthesis(i)
+        rights = generate_parenthesis(n - i - 1)
+        lefts.each do |left|
+            rights.each do |right|
+                combinations << "(" + left + ")" + right
+            end
+        end
+    end
+    combinations
+end
+```
+
+
+https://github.com/tokuhirat/LeetCode/pull/53/files#diff-edeaf9ab4fec143afff62d1f44e6f5d9ca2d7c345ff74d8c89f41ee178034827R81-R101
+使った括弧の数か、残りの括弧の数か。
diff --git a/22/step3.md b/22/step3.md
@@ -0,0 +1,27 @@
+# step3 3回続けて10分以内に書いてエラーを出さなければOKとする
+
+```ruby
+# @param {Integer} n
+# @return {String[]}
+def generate_parenthesis(n)
+    result = []
+    generate_parenthesis_helper = lambda do |left, right, parenthesis|
+        if right == n
+            result << parenthesis.join
+            return
+        end
+        if left < n
+            parenthesis << "("
+            generate_parenthesis_helper.call(left + 1, right, parenthesis)
+            parenthesis.pop
+        end
+        if right < left
+            parenthesis << ")"
+            generate_parenthesis_helper.call(left, right + 1, parenthesis)
+            parenthesis.pop
+        end
+    end
+    generate_parenthesis_helper.call(0, 0, [])
+    result
+end
+```
diff --git a/22/step4.md b/22/step4.md
@@ -0,0 +1 @@
+## step4 レビューを受けて解答を修正
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1 @@
		## step4 レビューを受けて解答を修正