回答編集履歴
2
過去の回答へのリンク追加
test
CHANGED
|
@@ -115,3 +115,6 @@
|
|
|
115
115
|
dp[-1]
|
|
116
116
|
end
|
|
117
117
|
```
|
|
118
|
+
---
|
|
119
|
+
過去に同じ問題に回答していたので、リンクを貼っておきます。(ただし言語はPython)
|
|
120
|
+
[combination sumを可読性の高いコードで計算する方法](https://teratail.com/questions/360119#reply-490932)
|
1
別の方法を思いついたので、そちらをメインとした説明を追加
test
CHANGED
|
@@ -1,4 +1,88 @@
|
|
|
1
1
|
Rubyはほとんど使ったことがないので、コードが拙いのはご容赦ください。あと、もっと良い方法があるかもしれません。
|
|
2
|
+
|
|
3
|
+
まずは候補を[2,3,6,7]に固定したコードを書いてみましょう。
|
|
4
|
+
|
|
5
|
+
2,3,6,7のそれぞれの使用回数について、そのすべての組み合わせを考えて、足した結果が target になるものを収集すればよさそうです。
|
|
6
|
+
target が 7 の場合、2の使用回数は0～3回のいずれかになるはずです。(4回だと target を超えてしまう)
|
|
7
|
+
ここで、最大回数は target を 2 で割った結果となることに注意しましょう。
|
|
8
|
+
同様に3の使用回数は0～2回、6の使用回数は0～1回、7の使用回数は0～1回のいずれかになるはずです。
|
|
9
|
+
|
|
10
|
+
これらをネストしたループで繰り返して、和が target になるものを収集すると考えると、以下のようなコードになります。
|
|
11
|
+
([2,2,3]が[7]の前に来るように、ループは逆順に回しています)
|
|
12
|
+
```ruby
|
|
13
|
+
def combination_sum(target)
|
|
14
|
+
result = []
|
|
15
|
+
(target / 2).downto(0) do |n2|
|
|
16
|
+
(target / 3).downto(0) do |n3|
|
|
17
|
+
(target / 6).downto(0) do |n6|
|
|
18
|
+
(target / 7).downto(0) do |n7|
|
|
19
|
+
if 2 * n2 + 3 * n3 + 6 * n6 + 7 * n7 == target
|
|
20
|
+
result << [2] * n2 + [3] * n3 + [6] * n6 + [7] * n7
|
|
21
|
+
end
|
|
22
|
+
end
|
|
23
|
+
end
|
|
24
|
+
end
|
|
25
|
+
end
|
|
26
|
+
result
|
|
27
|
+
end
|
|
28
|
+
```
|
|
29
|
+
|
|
30
|
+
さて、これを任意の候補でやりたいのですが、候補の数だけネストを深くしなければならないので、簡単にはいきません。
|
|
31
|
+
やり方としては、以下の2通りが考えられます。
|
|
32
|
+
|
|
33
|
+
1. Array の product を使う
|
|
34
|
+
2. 再帰を使う
|
|
35
|
+
|
|
36
|
+
まず 1. ですが、Array の product は、複数の配列から要素を選ぶ組み合わせのパターンをすべて列挙できます。
|
|
37
|
+
そのため、それぞれの候補の使用回数の配列を渡せば、1つのループで多重ループと同じことができます。
|
|
38
|
+
ただ、候補が1つもない場合は対応できないので別途処理する必要があります。
|
|
39
|
+
さらに、Array の product はやたらメモリを使うらしく、少し候補が増えると計算できなくなります。
|
|
40
|
+
```ruby
|
|
41
|
+
def combination_sum(candidates, target)
|
|
42
|
+
return (target == 0) ? [[]] : [] if candidates.empty?
|
|
43
|
+
result = []
|
|
44
|
+
as = candidates.map{|c| (target / c).downto(0).to_a}
|
|
45
|
+
a = as.shift
|
|
46
|
+
a.product(*as) do |ns|
|
|
47
|
+
if candidates.zip(ns).map{|c, n| c * n}.sum == target
|
|
48
|
+
result << candidates.zip(ns).map{|c, n| [c] * n}.sum([])
|
|
49
|
+
end
|
|
50
|
+
end
|
|
51
|
+
result
|
|
52
|
+
end
|
|
53
|
+
```
|
|
54
|
+
|
|
55
|
+
次に2.の再帰を使う方法についてですが、以下のページが詳しいです。
|
|
56
|
+
|
|
57
|
+
[よくやる再帰関数の書き方 〜 n 重 for 文を機械的に 〜](https://drken1215.hatenablog.com/entry/2020/05/04/190252)
|
|
58
|
+
|
|
59
|
+
こちらのページに従うと、以下のようなコードになります。(面倒なのでグローバル変数を使っています)
|
|
60
|
+
```ruby
|
|
61
|
+
def combination_sum(candidates, target)
|
|
62
|
+
$candidates = candidates
|
|
63
|
+
$target = target
|
|
64
|
+
$result = []
|
|
65
|
+
dfs([])
|
|
66
|
+
$result
|
|
67
|
+
end
|
|
68
|
+
|
|
69
|
+
def dfs(ns)
|
|
70
|
+
if ns.size == $candidates.size
|
|
71
|
+
if $candidates.zip(ns).map{|c, n| c * n}.sum == $target
|
|
72
|
+
$result << $candidates.zip(ns).map{|c, n| [c] * n}.sum([])
|
|
73
|
+
end
|
|
74
|
+
return
|
|
75
|
+
end
|
|
76
|
+
($target / $candidates[ns.size]).downto(0) do |n|
|
|
77
|
+
ns.push(n)
|
|
78
|
+
dfs(ns)
|
|
79
|
+
ns.pop
|
|
80
|
+
end
|
|
81
|
+
end
|
|
82
|
+
```
|
|
83
|
+
|
|
84
|
+
---
|
|
85
|
+
以下は以前の回答。
|
|
2
86
|
|
|
3
87
|
再帰を使う場合は以下のようになります。
|
|
4
88
|
候補から合計がtargetになる組み合わせを求める際には、候補の先頭の値を使う場合と使わない場合の2つに場合分けできます。
|