akmhmgc · akmhmgc · Oct 5, 2025 · potrue · Oct 5, 2025 · tokuhirat
diff --git a/78/step1.md b/78/step1.md
@@ -0,0 +1,27 @@
+# step1 何も見ずに解く
+[1,2,3] の例を考える。
+i番目までのsubsetsが決まっているとすると、i + 1番目までのsubsetsは
+i番目のsubsetsに、それぞれのsubsetにi + 1番目を加えたものになる。
+
+2までのsubsetsは
+[[],[1],[2],[1,2]]であり、3までのsubsetsを考えると
+[[],[1],[2],[1,2]]に3を加えた[[3],[1,3],[2,3],[1,2,3]]を合わせたものになる。
+要するに、i + 1番目の時点でi番目までのsubsetsはi + 1番目までのsubsetsの中でi + 1番目を入れていないsubsetsなので、入れたsubsetsを追加すれば良い。
+
+計算量を考える。
+k + 1番目の数字を入れる時は以下の処理を行う。
+i番目までのsubsetsは2^k個あり、それぞれのsubsetsにk + 1番目の数字を加えた新しいsubsetをつくって元のsubsetsに追加す
+subsetsの長さの平均をk / 2とすると、新しいsubsetsを追加するコストは(2^k) * (k / 2)となる。
+これを1からnのkまで考えるとO(n * 2^n)になりそう。
+空間計算量もsubsetの平均サイズを n / 2と考えて個数が2^nなのでO(n * 2^n)
+
+
+injectを使うとサクッと書けるので以下のようになった。
+
+```ruby
+# @param {Integer[]} nums
+# @return {Integer[][]}
+def subsets(nums)
+  nums.inject([[]]) { |subsets, num| subsets.concat(subsets.map { |subset| subset + [num] }) }
+end
+```
diff --git a/78/step2.md b/78/step2.md
@@ -0,0 +1,32 @@
+# step2 他の方の解答を見る
+
+## 再帰で解く
+https://github.com/tokuhirat/LeetCode/pull/51/
+
+pop()するところが難しいと感じたが、
+subsetにnums[i]を追加して、子に参照を渡して答えを出した後にpopする、と考えれば自然か。
+subsetsに追加するときに参照ではなく新しい配列を作らないとpopされて空のsubsetしか入っていないものが出力される。
+
+```ruby
+# @param {Integer[]} nums
+# @return {Integer[][]}
+def subsets(nums)
+    subsets_helper = lambda do
+        subsets = []
+        count_subsets = lambda do |i, subset|
+            if i == nums.size
+                subsets << subset[0..-1]
+                return
+            end
+
+            count_subsets.call(i + 1, subset)
+            subset << nums[i]
+            count_subsets.call(i + 1, subset)
+            subset.pop
+        end
+        count_subsets.call(0, [])
+        subsets
+    end
+    subsets_helper.call
+end
+```
diff --git a/78/step3.md b/78/step3.md
@@ -0,0 +1,21 @@
+# step3 3回続けて10分以内に書いてエラーを出さなければOKとする
+
+```ruby
+# @param {Integer[]} nums
+# @return {Integer[][]}
+def subsets(nums)
+    subsets = []
+    subsets_helper = lambda do |index, subset|
+        if index == nums.size
+            subsets << subset.dup
+            return
+        end
+        subsets_helper.call(index + 1, subset)
+        subset << nums[index]
+        subsets_helper.call(index + 1, subset)
+        subset.pop
+    end
+    subsets_helper.call(0, [])
+    subsets
+end
+```
diff --git a/78/step4.md b/78/step4.md
@@ -0,0 +1 @@
+## step4 レビューを受けて解答を修正
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1 @@
		## step4 レビューを受けて解答を修正