From 39cadd2c45c15960f5f558fa9e6afc3700905ea5 Mon Sep 17 00:00:00 2001
From: akmhmgc <akimuhamaguchi@icloud.com>
Date: Sat, 4 Oct 2025 21:57:56 +0900
Subject: [PATCH] 46

---
 46/step1.md | 32 +++++++++++++++++++++++++++++
 46/step2.md | 58 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 46/step3.md | 15 ++++++++++++++
 46/step4.md |  1 +
 4 files changed, 106 insertions(+)
 create mode 100644 46/step1.md
 create mode 100644 46/step2.md
 create mode 100644 46/step3.md
 create mode 100644 46/step4.md

diff --git a/46/step1.md b/46/step1.md
new file mode 100644
index 0000000..d23a966
--- /dev/null
+++ b/46/step1.md
@@ -0,0 +1,32 @@
+# step1 何も見ずに解く
+[1,2,3]の場合、
+[[]]
+[[1], [2], [3]]
+[[1, 2], [1, 3], [2, 3],[2, 1], [3, 1], [3, 2]]
+といった形で増やしていけば良さそう。
+つまり、配列の各permutationにまだ追加していない値があれば追加したものを加えるというループを繰り返してpermutationの長さがnumsのサイズになれば終了すれば良い。
+
+```ruby
+# @param {Integer[]} nums
+# @return {Integer[][]}
+def permute(nums)
+    permutations = [[]]
+    while permutations.first.size < nums.size
+        next_permutations = []
+        permutations.each do |permutation|
+            next_permutations.concat((nums - permutation).map { |num| (permutation + [num]) })
+        end
+        permutations = next_permutations
+    end
+    permutations
+end
+```
+
+ある時点でのpermutationの長さをkとすると、
+```
+(nums - permutation).map { |num| (permutation + [num]) }
+```
+の部分で(n - k) * kの計算量がかかる。
+これを各階層のノードの数とかけて0 - nのkについて合計すると、計算量はO(n * n!)になる。
+空間計算量は最終的に作られるpermutationの数 * 各permutationの長さなのでO(n * n!)
+nの最大値が6なので1秒以内で間に合うが、少しでも大きくなったらどうしようもなさそう。
diff --git a/46/step2.md b/46/step2.md
new file mode 100644
index 0000000..cacf243
--- /dev/null
+++ b/46/step2.md
@@ -0,0 +1,58 @@
+# step2 他の方の解答を見る
+
+## 使用中のnumsをSetにいれるかどうか
+https://github.com/Ryotaro25/leetcode_first60/pull/54#discussion_r1986035628
+
+numsの中でpermutationで使われていないものを取り出す時に線形に検索するとnが乗ってしまう。
+これは(Intersection of Two Arrays)[https://leetcode.com/problems/intersection-of-two-arrays/editorial/]と同じ話かと思った。
+
+https://github.com/tokuhirat/LeetCode/pull/50/files#r2278840164
+一方で、問題の制限はnが6以下であるし、オーバーヘッドを加味すると配列のまま計算する方が速いかもしれない。
+ハッシュテーブルにした方が速くなるくらいのサイズだとそもそも現実的な計算時間で終わらなくなっている気もするな…
+
+と思ってRubyのコードを読んだところ、特定の長さの配列まではハッシュテーブルを使わずに線形探索していた。
+そういえば積集合をとる`&`も同じことをしていたんだった。
+ref: https://github.com/ruby/ruby/blob/5257e1298c4dc4e854eaa0a9fe5e6dc5c1495c91/array.c#L5558-L5583
+
+## 再帰で解く
+https://github.com/ryosuketc/leetcode_arai60/pull/39
+
+```ruby
+# @param {Integer[]} nums
+# @return {Integer[][]}
+def permute(nums)
+    permute_helper = lambda do |nums|
+        permutes = []
+        append_permutes = lambda do |permute, nums|
+            if nums.empty?
+                permutes << permute 
+                return
+            end
+            nums.each_with_index do |num, i|
+                new_permute = permute + [num]
+                new_nums = nums[0...i] + nums[(i + 1)..-1]
+                append_permutes.call(new_permute, new_nums)
+            end
+        end
+        append_permutes.call([], nums)
+        permutes
+    end
+    permute_helper.call(nums)
+end
+```
+
+## step1の改善
+
+```ruby
+# @param {Integer[]} nums
+# @return {Integer[][]}
+def permute(nums)
+    permutes = [[]]
+    while permutes.first.size != nums.size
+        permutes = permutes.each_with_object([]) do |permute, next_permutes|
+            next_permutes.concat((nums - permute).map { |num| permute + [num] })
+        end
+    end
+    permutes
+end
+```
diff --git a/46/step3.md b/46/step3.md
new file mode 100644
index 0000000..41c25f3
--- /dev/null
+++ b/46/step3.md
@@ -0,0 +1,15 @@
+# step3 3回続けて10分以内に書いてエラーを出さなければOKとする
+
+```ruby
+# @param {Integer[]} nums
+# @return {Integer[][]}
+def permute(nums)
+    permutes = [[]]
+    while permutes.first.size != nums.size
+        permutes = permutes.each_with_object([]) do |permute, next_permutes|
+            next_permutes.concat((nums - permute).map { |num| permute + [num] })
+        end
+    end
+    permutes
+end
+```
diff --git a/46/step4.md b/46/step4.md
new file mode 100644
index 0000000..5941ee1
--- /dev/null
+++ b/46/step4.md
@@ -0,0 +1 @@
+## step4 レビューを受けて解答を修正