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

Question

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

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

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

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

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

＊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

１）自分で書いたコード

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

２）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

Answer 1

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

可読性高いコード

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

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

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

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

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

動的計画法

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

Answer 2

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

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

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

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

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

2
────
0(0)
1(2)
2(4)
3(6)

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

2 3
──────
0┬0(0)
 ├1(3)
 └2(6)
1┬0(2)
 └1(5)
2┬0(4)
 └1(7)
3─0(6)

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

2 3 6 7
──────────
0┬0┬0┬0(0)
 │ │ └1(7)
 │ └1─0(6)
 ├1─0─0(3)
 └2─0─0(6)
1┬0─0─0(2)
 └1─0─0(5)
2┬0─0─0(4)
 └1─0─0(7)
3─0─0─0(6)

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

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

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

c = 2
tmps = []

tmp = []
while target >= sum(tmp):
    tmps.append(tmp.copy())
    tmp.append(c)

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

c = 3
tmps = []

tmp = []
while target >= sum(tmp):
    tmps.append(tmp.copy())
    tmp.append(c)
tmp = [2]
while target >= sum(tmp):
    tmps.append(tmp.copy())
    tmp.append(c)
tmp = [2,2]
while target >= sum(tmp):
    tmps.append(tmp.copy())
    tmp.append(c)
tmp = [2,2,2]
while target >= sum(tmp):
    tmps.append(tmp.copy())
    tmp.append(c)

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

c = 2
tmps = []

tmp = []
while target >= sum(tmp):
    tmps.append(tmp.copy())
    tmp.append(c)
prev_tmps = tmps

c = 3
tmps = []

for tmp in prev_tmps:
    while target >= sum(tmp):
        tmps.append(tmp.copy())
        tmp.append(c)

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

prev_tmps = [[]]

c = 2
tmps = []

for tmp in prev_tmps:
    while target >= sum(tmp):
        tmps.append(tmp.copy())
        tmp.append(c)
prev_tmps = tmps

c = 3
tmps = []

for tmp in prev_tmps:
    while target >= sum(tmp):
        tmps.append(tmp.copy())
        tmp.append(c)
prev_tmps = tmps

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

prev_tmps = [[]]
for c in candidates:
    tmps = []
    for tmp in prev_tmps:
        while target >= sum(tmp):
            tmps.append(tmp.copy())
            tmp.append(c)
    prev_tmps = tmps

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

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

def combinationSum(candidates, target):
    prev_tmps = [[]]
    for c in candidates:
        tmps = []
        for tmp in prev_tmps:
            while target >= sum(tmp):
                tmps.append(tmp.copy())
                tmp.append(c)
        prev_tmps = tmps
    output = []
    for tmp in prev_tmps:
        if sum(tmp) == target:
            output.append(tmp)
    return output

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

def combinationSum(candidates, target):
    prev_tmps = [[]]
    output = []
    for c in candidates:
        tmps = []
        for tmp in prev_tmps:
            while target > sum(tmp):
                tmps.append(tmp.copy())
                tmp.append(c)
            if sum(tmp) == target:
                output.append(tmp)
        prev_tmps = tmps
    return output

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

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

def combinationSum(candidates, target):
    if target == 0:
        return [[]]
    elif target < 0 or not candidates:
        return []
    else:
        c = candidates[:1]
        return [c + l for l in combinationSum(candidates, target - c[0])] + combinationSum(candidates[1:], target)

---

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

def debug(depth, msg):
    print('   ' * depth + msg)

def combinationSum(candidates, target, depth = 0):
    debug(depth, f"def combinationSum({candidates}, {target}):")
    if target == 0:
        debug(depth, f"return [[]]")
        return [[]]
    elif target < 0 or not candidates:
        debug(depth, f"return []")
        return []
    else:
        debug(depth, f"c = {candidates}[:1]")
        c = candidates[:1]
        debug(depth, f"=> c = {c}")
        debug(depth, f"ret1 = combinationSum({candidates}, {target} - {c}[0])")
        ret1 = combinationSum(candidates, target - c[0], depth + 1)
        debug(depth, f"=> ret1 = {ret1}")
        debug(depth, f"ret2 = [{c} + l for l in {ret1}]")
        ret2 = [c + l for l in ret1]
        debug(depth, f"=> ret2 = {ret2}")
        debug(depth, f"ret3 = combinationSum({candidates}[1:], {target})")
        ret3 = combinationSum(candidates[1:], target, depth + 1)
        debug(depth, f"=> ret3 = {ret3}")
        debug(depth, f"return {ret2} + {ret3}")
        return ret2 + ret3

print(combinationSum([1], 2))

出力例

def combinationSum([1], 2):
c = [1][:1]
=> c = [1]
ret1 = combinationSum([1], 2 - [1][0])
   def combinationSum([1], 1):
   c = [1][:1]
   => c = [1]
   ret1 = combinationSum([1], 1 - [1][0])
      def combinationSum([1], 0):
      return [[]]
   => ret1 = [[]]
   ret2 = [[1] + l for l in [[]]]
   => ret2 = [[1]]
   ret3 = combinationSum([1][1:], 1)
      def combinationSum([], 1):
      return []
   => ret3 = []
   return [[1]] + []
=> ret1 = [[1]]
ret2 = [[1] + l for l in [[1]]]
=> ret2 = [[1, 1]]
ret3 = combinationSum([1][1:], 2)
   def combinationSum([], 2):
   return []
=> ret3 = []
return [[1, 1]] + []
[[1, 1]]

Comments

[sequelanonymous]

詳細なわかりやすい解答ありがとうございます。すっと理解できました。treeで表現して理解しようとしていから余計に理解できなくなっていたことに気づけました。

こちら、もしactorbugさんがツリー構造で表現しようとしたら、ルートにempty nodeを置いて、次に2,3,6,7のそれぞれのchild nodeを生やしていって、記載頂いた行列のようなつながりを作り、実装に落とし込む感じでしょうか？
今回のような組み合わせ問題の場合、treeで表現しようとすると、重複ノードがでたりtreeそのものが肥大化して余計わかりづらい気がしたので組み合わせ問題の場合は、actorbugさんのように行列で考えるのがいいのかなと思いました。

また、最後に追記して頂いた`私ならこう書く`のコードがとても理解しやすそうで一点確認させてください。
`combinationSum(candidates, target - c[0])] + combinationSum(candidates[1:], target)`の箇所がトラックできずにりますが、どう言語化して理解したらいいでしょうか？

[actorbug]

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

[sequelanonymous]

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

[actorbug]

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

[actorbug]

「基本的な考え方」の最後の図をみれば、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]

一応、今回の再帰関数を作成した過程を再現してみます。
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]

詳細なステップありがとうございます。
私の方でもコードを動かしながらデバックしてトレースしてみてるのですが、2-1, 2-2の処理部分でどうしても頭の中が途中で追いかけられなくなります。
このコードをどうやってデバックしたり、頭の中で数値をトラックしたのか、不思議に思ってしまうぐらいなのですが、慣れの問題でしょうか？私もactorbugさんのようにこういったコードをかけるようになりたいのですが、どう学ばられたのか教えていただけませんでしょうか？

私の場合は、再帰的に呼び出す関数が一つだけなら何とか実装できるのですが、2つに増えた途端(まさに書いて頂いた最後のコードのような場合)、実装が思いつかないどころか、実装されたコードを読むことさえ時間がすごくかかるようになってしまいます。

[actorbug]

再帰は、Schemeという言語を通して学びましたが、最近ではあまり人がいないかもしれません。
以下のリンク先を見れば、Schemeの雰囲気が分かるかもしれません。

なんでも再帰
http://practical-scheme.net/docs/tailcall-j.html

ただ、お望みの知識が得られるかどうかはわかりません。

[sequelanonymous]

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

こちらの質問は、一旦actorbugさんの解答をベストアンサーとして閉じようと思います。詳細なご説明ありがとうございました。