akmhmgc · akmhmgc · Oct 5, 2025 · tokuhirat · Oct 5, 2025 · akmhmgc
diff --git a/39/step1.md b/39/step1.md
@@ -0,0 +1,34 @@
+# step1 何も見ずに解く
+前から値を見ていって、その値あるいはそれより右にある値をcandidateに入れて次に渡す。
+次の人は入れた値あるいはそれより右にある値からcandidateに入れる値を選択しなくてはならない。
+という感じで行けそう。
+
+targetをcandidatesの最も小さい値で割った分だけ探索の深さが増えるので
+candidatesの要素数をN、candidatesの最小値をCmとするとN^(target / Cm)くらいまで計算量が膨らむのではないか？
+
+こういう多項式時間ではない計算量の見積もりはした方が良いのか悩む。
+現実だと、入力の上限が変わったら容易に現実的な時間で計算が終わりそうにないことと、そもそも要件を変えることができないかを考える気がする。
+計算量の見積もりをオーダー記法で考えるより、入力サイズを変えてみて答えを返すまでの許容できる閾値を探るかもしれない。
+
+```ruby
+# @param {Integer[]} candidates
+# @param {Integer} target
+# @return {Integer[][]}
+def combination_sum(candidates, target)
+    combinations = []
+    combination_sum_helper = lambda do |index, candidate|
+        return if candidate.sum > target
+        if candidate.sum == target
+            combinations << candidate.dup
+            return
+        end
+        (index...(candidates.size)).each do |next_index|
+            candidate << candidates[next_index]
+            combination_sum_helper.call(next_index, candidate)
+            candidate.pop
+        end
+    end
+    combination_sum_helper.call(0, [])
+    combinations
+end
+```
diff --git a/39/step2.md b/39/step2.md
@@ -0,0 +1,131 @@
+# step2 他の方の解答を見る
+## 計算量
+https://github.com/Mike0121/LeetCode/pull/1#discussion_r1578212926
+
+計算量は全くわからないので一旦考えないことにした。興味が出たら読む。
+
+## step1の改善
+https://github.com/fhiyo/leetcode/pull/52
+
+step1ではtotalをいちいち計算していたが引数に渡すこともできる。
+また、[a,b,c,d]と昇順にソートしておけば、bを追加した時に合計がtarget以上になった場合それ以降は探索する必要がなくなる。
+
+```ruby
+# @param {Integer[]} candidates
+# @param {Integer} target
+# @return {Integer[][]}
+def combination_sum(candidates, target)
+    sorted_candidates = candidates.sort
+    combinations = []
+    combination_sum_helper = lambda do |index, total, candidate|
+        if total == target
+            combinations << candidate.dup
+            return
+        end
+        (index...(sorted_candidates.size)).each do |next_index|
+            new_total = total + sorted_candidates[next_index]
+            break if new_total > target
+
+            candidate << sorted_candidates[next_index]
+            combination_sum_helper.call(next_index, new_total, candidate)
+            candidate.pop
+        end
+    end
+    combination_sum_helper.call(0, 0, [])
+    combinations
+end
+```
+candidateを再帰関数のなかで持たない書き方もできる。
+できるけど個人的にわざわざ`combination_sum_helper`の外に露出させるメリットを感じなかった。
+
+```ruby
+# @param {Integer[]} candidates
+# @param {Integer} target
+# @return {Integer[][]}
+def combination_sum(candidates, target)
+    sorted_candidates = candidates.sort
+    combinations = []
+    partial_combination = []
+    combination_sum_helper = lambda do |index, total|
+        if total == target
+            combinations << partial_combination.dup
+            return
+        end
+        (index...(sorted_candidates.size)).each do |next_index|
+            new_total = total + sorted_candidates[next_index]
+            break if new_total > target
+
+            partial_combination << sorted_candidates[next_index]
+            combination_sum_helper.call(next_index, new_total)
+            partial_combination.pop
+        end
+    end
+    combination_sum_helper.call(0, 0)
+    combinations
+end
+```
+
+## 他のバックトラックの思考法
+https://github.com/fhiyo/leetcode/pull/52#discussion_r1690161771
+step1を他のバックトラックの思考法で書いてみる。
+(step1で合計値を毎回計算している部分は改善していない)
+
+> B を一つ使うか、C 以降しか使ってはいけないか、に分岐する。
+
+```ruby
+# @param {Integer[]} candidates
+# @param {Integer} target
+# @return {Integer[][]}
+def combination_sum(candidates, target)
+    combinations = []
+    combination_sum_helper = lambda do |index, candidate|
+        return if candidate.sum > target
+        if candidate.sum == target
+            combinations << candidate.dup
+            return
+        end
+
+        # 同じindexの値を使う
+        candidate << candidates[index]
+        combination_sum_helper.call(index, candidate)
+        candidate.pop
+
+        # 次のindexの値を使う
+        return if index + 1 >= candidates.size
+        combination_sum_helper.call(index + 1, candidate)
+    end
+    combination_sum_helper.call(0, [])
+    combinations
+end
+```
+
+> B の使う数を列挙して分岐し、C 以降しか使ってはいけないに遷移する。
+
+```ruby
+# @param {Integer[]} candidates
+# @param {Integer} target
+# @return {Integer[][]}
+def combination_sum(candidates, target)
+    combinations = []
+    combination_sum_helper = lambda do |index, total, partial_combination|
+        if total == target
+            combinations << partial_combination.dup
+            return
+        end
+        return unless index < candidates.size
+        max_usage = (target - total) / candidates[index]
+        (1..max_usage).each do |i|
+            new_total = total + candidates[index] * i
+            i.times { partial_combination << candidates[index] }
+            combination_sum_helper.call(index + 1, new_total, partial_combination)
+            i.times { partial_combination.pop }
+        end
+        combination_sum_helper.call(index + 1, total, partial_combination)
+    end
+    combination_sum_helper.call(0, 0, [])
+    combinations
+end
+```
+
+色々考え方があって面白い。
+「要するに抜け漏れなく分類できていればよくて、パターンは複数考えられる」という抽象度の高い理解が出来ているといろんな人のコードが早く読めるようになるし、自分のコードも自由に書き換えられる。
diff --git a/39/step3.md b/39/step3.md
@@ -0,0 +1,26 @@
+# step3 3回続けて10分以内に書いてエラーを出さなければOKとする
+
+```ruby
+# @param {Integer[]} candidates
+# @param {Integer} target
+# @return {Integer[][]}
+def combination_sum(candidates, target)
+    combinations = []
+    combination_sum_helper = lambda do |index, total, partial_combination|
+        if total == target
+            combinations << partial_combination.dup
+            return
+        end
+        (index...(candidates.size)).each do |next_index|
+            new_total = total + candidates[next_index]
+            next if new_total > target
+
+            partial_combination << candidates[next_index]
+            combination_sum_helper.call(next_index, new_total, partial_combination)
+            partial_combination.pop
+        end
+    end
+    combination_sum_helper.call(0, 0, [])
+    combinations
+end
+```
diff --git a/39/step4.md b/39/step4.md
@@ -0,0 +1 @@
+## step4 レビューを受けて解答を修正
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1 @@
		## step4 レビューを受けて解答を修正