質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.54%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

データ構造

データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

コードレビュー

コードレビューは、ソフトウェア開発の一工程で、 ソースコードの検査を行い、開発工程で見過ごされた誤りを検出する事で、 ソフトウェア品質を高めるためのものです。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

Q&A

解決済

2回答

1855閲覧

combination sumを可読性の高いコードで計算する方法

sequelanonymous

総合スコア123

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

データ構造

データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

コードレビュー

コードレビューは、ソフトウェア開発の一工程で、 ソースコードの検査を行い、開発工程で見過ごされた誤りを検出する事で、 ソフトウェア品質を高めるためのものです。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

0グッド

0クリップ

投稿2021/09/18 05:11

下記の問題を可読性高いコードで解きたいと思っています。1)自分で書いたコードでは、途中まで書くことができましたが、書ききれていません。どう試行錯誤してもこのコードをベースに進んでみても解答にたどり着くことができません。

もし、この書き方からどう展開していっても解決には至らない、根本的に違う明確な理由にお気づきの方いましたら、理由をご教示いただけませんしょうか?

もし、この先こう書いたら正解にたどり着くことできる、というのがあれば、コードベースでご教示いただけませんしょうか?

また、2)backtrakingを用いた解答では、backtrackingを用いて完答しました。こちらの書き方は、コードリーディングがしづらく、「知っていたから解けた」「覚えていたから解けた」、というような解答になります。
未だに、問題文からこの解答にたどり着くステップが思いつくことができません。それを思いつくために、まずは、recurionをつかわずに解答しようと思い、1)自分で書いたコードを書き始めました。

もし、こちらの解答についても、こう理解したらすっと解答できる、というようなコツなどありましたらご教示いただけると助かります。

*backtrackingがなにか、backtrackingは、dfsでtraverseするので再帰つかう、などのテクニック的なところが知りたい、というよりは、下記の問題文からどうやってツリーで探索空間としての表現が思いつくか、それをどう実装に落とし込めるかに気づくことができたか、について知りたいと思っています。

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

39. Combination Sum

1)自分で書いたコード

from collections import deque class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: # [2,3,6,7] # [2,2,2,2] -> [2,2,3] = target # [3,3,3] -> [3,3,2] # [6,6] -> [6,2] -> [6,3] # [7] = target candidates.sort() tmp = deque() output = [] for c in candidates: # 2,3,6 while target > sum(tmp): # [2,2,3,6] tmp.append(c) # [2,2,2,2] -> 8 # [2,2,2,3] -> 9 while target < sum(tmp): # 7 < 7 tmp.popleft() # [2,2,2] # [2,2,3] if sum(tmp) == target: # 6 == 7 output.append(tmp) # [2,2,3] tmp.popleft() return output

2)backtrakingを用いた解答

res = [] def dfs(i, cur, total): # (0, [], 0), (0, [2], 2).... (0, [2,2,2,2], 8)......(1, [2,2,2], 6) if total == target: # 0 == 7, 2 == 7 res.append(cur.copy()) return if i >= len(candidates) or total > target: # 0>=4 or 0>7, 0>=4 or 2>7, 8>7 return cur.append(candidates[i]) # [2,2].....[2,2,3] # currのリストには、足したものたちをいれていく。 dfs(i, cur, total+candidates[i]) #(0, [2], 2),(0, [2,2], 4), ....(0, [2,2,2], 6) ....(1, [2,2,3], 7) cur.pop() # (0, [2,2,2,2], 8) -> (0, [2,2,2], 6) dfs(i+1, cur, total) # (1, [2,2,2], 6) dfs(0, [], 0) return res

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

2

あまりまとまりの無い回答(というかコメント)になります。

可読性高いコード

コードの可読性が高いかどうかというのは、ある程度読み手のスキルに依るところが大きいです。
特にこういう探索系の処理については、定番のアルゴリズムがあり、それを知っていればそれほど難しくはありません。
「知っていれば解けた」が正しいです。

理由をご教示
この先こう書いたら正解にたどり着くことできる

コードを見てもどのようなアルゴリズムなのかよくわかりません。
アルゴリズムを最後まで文章で書いてみていただければ、アドバイスできるかもしれません。 もしかしたら、書いている途中でご自分で気がつくかもしれませんね。

下記の問題文からどうやってツリーで探索空間としての表現が思いつくか

こういう詰め込み系の問題は、こういうアルゴリズムでは定番です。
なので、アルゴリズムを勉強していれば、思い付きます。

動的計画法

なので、こういう問題の開放を思い付きたいのであれば、アルゴリズムの勉強をしてみるのがいいでしょう。

投稿2021/09/18 13:28

TakaiY

総合スコア12558

yudedako67, maisumakun👍を押しています

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

1

ベストアンサー

1)のソースをベースにしようとしましたが、跡形もなくなってしまったので、最初から説明します。

まずは、基本的な考え方から説明しましょう。

[2,3,6,7]内の数字を何回か足し合わせて7を作るという問題ですが、
それぞれの数字の使用回数の組み合わせがどれだけあるか、すべて書き出してみましょう。

まずは、先頭の2のみを使う場合を考えると、使用回数は、0回、1回、2回、3回の4パターンあります。
(4回以上だと、目的の数値を超えてしまうので対象外です)

これを以下のように表現してみましょう。
(数値は使用回数、右端のカッコ内が合計)

text

12 2──── 30(0) 41(2) 52(4) 63(6)

次に、23の2つのみを使う場合の使用回数を考えます。
2のそれぞれの使用回数について、3がいくつ使えるかを調べると、以下のようになります。

text

12 3 2────── 30┬0(0) 4 ├1(3) 5 └2(6) 61┬0(2) 7 └1(5) 82┬0(4) 9 └1(7) 103─0(6)

同様に7まで続ければ、最終的に以下のようになります。

text

12 3 6 7 2────────── 30┬0┬0┬0(0) 4 │ │ └1(7) 5 │ └1─0(6) 6 ├1─0─0(3) 7 └2─0─0(6) 81┬0─0─0(2) 9 └1─0─0(5) 102┬0─0─0(4) 11 └1─0─0(7) 123─0─0─0(6)

あとは、合計が7になるものをとりだせば完了です。

つぎに、これをコードに落とし込んでいきましょう。

まずは、先頭の2のみの場合は簡単でしょう。(tmpsという変数に結果を集めるものとします)

python

1c = 2 2tmps = [] 3 4tmp = [] 5while target >= sum(tmp): 6 tmps.append(tmp.copy()) 7 tmp.append(c)

次に、23を使う場合ですが、2のみの場合の結果それぞれについて、やっていけばよいでしょう。

python

1c = 3 2tmps = [] 3 4tmp = [] 5while target >= sum(tmp): 6 tmps.append(tmp.copy()) 7 tmp.append(c) 8tmp = [2] 9while target >= sum(tmp): 10 tmps.append(tmp.copy()) 11 tmp.append(c) 12tmp = [2,2] 13while target >= sum(tmp): 14 tmps.append(tmp.copy()) 15 tmp.append(c) 16tmp = [2,2,2] 17while target >= sum(tmp): 18 tmps.append(tmp.copy()) 19 tmp.append(c)

前回のtmpsprev_tmpsという名前で参照できるようにすれば、ループにまとめることができます。

python

1c = 2 2tmps = [] 3 4tmp = [] 5while target >= sum(tmp): 6 tmps.append(tmp.copy()) 7 tmp.append(c) 8prev_tmps = tmps 9 10c = 3 11tmps = [] 12 13for tmp in prev_tmps: 14 while target >= sum(tmp): 15 tmps.append(tmp.copy()) 16 tmp.append(c)

c = 2の場合とc = 3の場合のソースをそろえるため、事前にprev_tmps[[]]を入れておきます。

python

1prev_tmps = [[]] 2 3c = 2 4tmps = [] 5 6for tmp in prev_tmps: 7 while target >= sum(tmp): 8 tmps.append(tmp.copy()) 9 tmp.append(c) 10prev_tmps = tmps 11 12c = 3 13tmps = [] 14 15for tmp in prev_tmps: 16 while target >= sum(tmp): 17 tmps.append(tmp.copy()) 18 tmp.append(c) 19prev_tmps = tmps

これで、ccandidateで繰り返す形に持ち込めました。

python

1prev_tmps = [[]] 2for c in candidates: 3 tmps = [] 4 for tmp in prev_tmps: 5 while target >= sum(tmp): 6 tmps.append(tmp.copy()) 7 tmp.append(c) 8 prev_tmps = tmps

最後に、合計がtargetのものを収集すれば完成です。

すべてまとめると、以下のようになります。

python

1def combinationSum(candidates, target): 2 prev_tmps = [[]] 3 for c in candidates: 4 tmps = [] 5 for tmp in prev_tmps: 6 while target >= sum(tmp): 7 tmps.append(tmp.copy()) 8 tmp.append(c) 9 prev_tmps = tmps 10 output = [] 11 for tmp in prev_tmps: 12 if sum(tmp) == target: 13 output.append(tmp) 14 return output

targetと等しくなった時点で以降の処理が不要になることを利用すれば、もう少し1)のソースに近くなります。

python

1def combinationSum(candidates, target): 2 prev_tmps = [[]] 3 output = [] 4 for c in candidates: 5 tmps = [] 6 for tmp in prev_tmps: 7 while target > sum(tmp): 8 tmps.append(tmp.copy()) 9 tmp.append(c) 10 if sum(tmp) == target: 11 output.append(tmp) 12 prev_tmps = tmps 13 return output

2)のソースについては、dfs(i, cur, total+candidates[i])が現在の数字の使用回数を増やす方向、dfs(i+1, cur, total)が次の数字の処理に移行する方向と考えれば、理解できるのではないでしょうか。

余談ですが、私ならこう書く、というソースを載せておきます。

python

1def combinationSum(candidates, target): 2 if target == 0: 3 return [[]] 4 elif target < 0 or not candidates: 5 return [] 6 else: 7 c = candidates[:1] 8 return [c + l for l in combinationSum(candidates, target - c[0])] + combinationSum(candidates[1:], target)

念のため、上記ソースの詳細ログ出力バージョンを載せておきます。
呼び出しが深くなるごとにインデントを増やしているので、多少は追いやすいはずです。

python

1def debug(depth, msg): 2 print(' ' * depth + msg) 3 4def combinationSum(candidates, target, depth = 0): 5 debug(depth, f"def combinationSum({candidates}, {target}):") 6 if target == 0: 7 debug(depth, f"return [[]]") 8 return [[]] 9 elif target < 0 or not candidates: 10 debug(depth, f"return []") 11 return [] 12 else: 13 debug(depth, f"c = {candidates}[:1]") 14 c = candidates[:1] 15 debug(depth, f"=> c = {c}") 16 debug(depth, f"ret1 = combinationSum({candidates}, {target} - {c}[0])") 17 ret1 = combinationSum(candidates, target - c[0], depth + 1) 18 debug(depth, f"=> ret1 = {ret1}") 19 debug(depth, f"ret2 = [{c} + l for l in {ret1}]") 20 ret2 = [c + l for l in ret1] 21 debug(depth, f"=> ret2 = {ret2}") 22 debug(depth, f"ret3 = combinationSum({candidates}[1:], {target})") 23 ret3 = combinationSum(candidates[1:], target, depth + 1) 24 debug(depth, f"=> ret3 = {ret3}") 25 debug(depth, f"return {ret2} + {ret3}") 26 return ret2 + ret3 27 28print(combinationSum([1], 2))

出力例

text

1def combinationSum([1], 2): 2c = [1][:1] 3=> c = [1] 4ret1 = combinationSum([1], 2 - [1][0]) 5 def combinationSum([1], 1): 6 c = [1][:1] 7 => c = [1] 8 ret1 = combinationSum([1], 1 - [1][0]) 9 def combinationSum([1], 0): 10 return [[]] 11 => ret1 = [[]] 12 ret2 = [[1] + l for l in [[]]] 13 => ret2 = [[1]] 14 ret3 = combinationSum([1][1:], 1) 15 def combinationSum([], 1): 16 return [] 17 => ret3 = [] 18 return [[1]] + [] 19=> ret1 = [[1]] 20ret2 = [[1] + l for l in [[1]]] 21=> ret2 = [[1, 1]] 22ret3 = combinationSum([1][1:], 2) 23 def combinationSum([], 2): 24 return [] 25=> ret3 = [] 26return [[1, 1]] + [] 27[[1, 1]]

投稿2021/09/18 14:52

編集2021/09/20 13:09
actorbug

総合スコア2203

lehshell👍を押しています

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

sequelanonymous

2021/09/19 03:18

詳細なわかりやすい解答ありがとうございます。すっと理解できました。treeで表現して理解しようとしていから余計に理解できなくなっていたことに気づけました。 こちら、もしactorbugさんがツリー構造で表現しようとしたら、ルートにempty nodeを置いて、次に2,3,6,7のそれぞれのchild nodeを生やしていって、記載頂いた行列のようなつながりを作り、実装に落とし込む感じでしょうか? 今回のような組み合わせ問題の場合、treeで表現しようとすると、重複ノードがでたりtreeそのものが肥大化して余計わかりづらい気がしたので組み合わせ問題の場合は、actorbugさんのように行列で考えるのがいいのかなと思いました。 また、最後に追記して頂いた`私ならこう書く`のコードがとても理解しやすそうで一点確認させてください。 `combinationSum(candidates, target - c[0])] + combinationSum(candidates[1:], target)`の箇所がトラックできずにりますが、どう言語化して理解したらいいでしょうか?
actorbug

2021/09/19 10:10

「基本的な考え方」の最後の図を、そのまま木構造とみなすことができます。 一番左上が根、+の前が下方向、後ろが右方向になります。
sequelanonymous

2021/09/19 10:34

お返事ありがとうございます。 すみません、どの数字がルートで子ノードなりますでしょうか? 一つのツリーだけでは表現できないような気がしたのでご確認させて頂きました。
actorbug

2021/09/19 10:39

左上の0がルートノードと書いたはずです。 その真下の1と、その右の0が、その直接の子ノードとなります。
actorbug

2021/09/19 20:43

「基本的な考え方」の最後の図をみれば、4つの木があることが分かります。 その上にルートノードがあるとみなせば、1つの大きな木であるとみなすことはできるでしょう。 そこから「N進木の二分木表現」で二分木に変換したものが、この再帰関数でたどるツリー構造になります。 https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%9C%A8#N%E9%80%B2%E6%9C%A8%E3%81%AE%E4%BA%8C%E5%88%86%E6%9C%A8%E8%A1%A8%E7%8F%BE +の前が「次の兄弟」、後ろが「最初の子」にあたります。 ちなみに、2)のソースも全く同じ構造で、最初の再帰呼び出しが「次の兄弟」、次が「最初の子」にあたります。 ただ、そもそもの話をすると、再帰関数を書く際にツリー構造を意識して書くようなことはしていません。 前にも説明しましたが、すでに実装が終わっているものとみなして、それを利用して書いているという感覚です。 だから、木構造で説明してほしいと言われても、後付けで再帰がたどる木構造を説明するだけになるので、それが再帰関数を自前で書くのに有用だとは思いません。
actorbug

2021/09/19 21:31

一応、今回の再帰関数を作成した過程を再現してみます。 1. combinationSum([2,3,6,7],7)を計算したい 2. まずは候補の先頭の数字を使うか、使わないかで場合分けができそう 2-1. 先頭の数字を使わない場合は、単に候補の先頭を除いたcombinationSum([3,6,7],7)で計算できそう 2-2. 先頭の数字を使う場合は、候補は先頭の数字をまだ使うかもしれないので変えず、  目標の数値は先頭の数字の分だけ減るので、まずはcombinationSum([2,3,6,7],5)を計算しよう  あとはその結果それぞれに、先頭の数字を追加してやれば、求める結果になるはず 3. 2-1,2-2の結果をまとめれば、求める結果になりそう(ここで最後のelse:以下のコードが完成) 4. あとは停止条件を決めないといけないな 4-1. まずは目標の数値がマイナスになってしまった場合。これは無理なので結果なしの[]を返そう 4-2. 次は目標の数値が0の場合。これは候補を一切足さなくてもOKなので空の結果を含む[[]]を返そう 4-3. 最後に、候補が無くなった場合。これは目標の数値が0ならいけるので[[]]を、違うなら無理なので[]を返そう 5. 4-1~4-3をまとめると、まず目標の数値が0かを判定して、その後にそれ以外を判定したほうがよさそうだな(完成)
sequelanonymous

2021/09/20 05:04

詳細なステップありがとうございます。 私の方でもコードを動かしながらデバックしてトレースしてみてるのですが、2-1, 2-2の処理部分でどうしても頭の中が途中で追いかけられなくなります。 このコードをどうやってデバックしたり、頭の中で数値をトラックしたのか、不思議に思ってしまうぐらいなのですが、慣れの問題でしょうか?私もactorbugさんのようにこういったコードをかけるようになりたいのですが、どう学ばられたのか教えていただけませんでしょうか? 私の場合は、再帰的に呼び出す関数が一つだけなら何とか実装できるのですが、2つに増えた途端(まさに書いて頂いた最後のコードのような場合)、実装が思いつかないどころか、実装されたコードを読むことさえ時間がすごくかかるようになってしまいます。
actorbug

2021/09/20 06:07

再帰は、Schemeという言語を通して学びましたが、最近ではあまり人がいないかもしれません。 以下のリンク先を見れば、Schemeの雰囲気が分かるかもしれません。 なんでも再帰 http://practical-scheme.net/docs/tailcall-j.html ただ、お望みの知識が得られるかどうかはわかりません。
sequelanonymous

2021/09/20 08:28 編集

ありがとうございます。読んでみましたが、少し私には難しかったです。 上記コードに関して、もう少しシンプルにしてデバックしてみました。まだ少し不明な箇所があったので下記で新しく質問をたてました。もし、ご回答可能でしたら解答していただけますと幸いです。 https://teratail.com/questions/360453?modal=q-comp こちらの質問は、一旦actorbugさんの解答をベストアンサーとして閉じようと思います。詳細なご説明ありがとうございました。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.54%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

同じタグがついた質問を見る

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

データ構造

データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

コードレビュー

コードレビューは、ソフトウェア開発の一工程で、 ソースコードの検査を行い、開発工程で見過ごされた誤りを検出する事で、 ソフトウェア品質を高めるためのものです。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。