部分和と向き合ってみる

こんばんは。
お久しぶりです(*´ω｀)

今回のチャンレンジは、任意の要素を含んだ配列の中から
無作為に要素を選んで、合算します。
しかし、ただ合算すれば良いのではなく、
目標値になるように合算しなければなりません。

例えば、合計が 20になるように配列の中から組み合わせを選んでください!!
っというものです。

ややこい(;´･ω･)

かなり有名で基礎的な内容のようですが、
個人的には手こずりました(笑)

いきなりですけど、
コードを載せちゃいます。

```Partial_sum.py
def solve(Nlist, target,  i=0, sum=0):
    if i == len(Nlist):
        return sum == target
    if (solve(Nlist, target, i + 1, sum)):
        return True
    if (solve(Nlist, target, i + 1, sum + Nlist[i])):
        return True
    return False

Nlist = [1,3,5,12,7]
target = 11
print(solve(Nlist, target))
```

思ったよりシンプルですが、動きは複雑です。
例えばですが、
最初はここだけ見ます。

```Partial_sum.py
#ここから start!! 
Nlist = [1,3,5,12,7]
target = 11
#          ↓[1,3,4...] ↓ 11
print(solve(Nlist, target))
```

solve の中に、Nlist と target を放り込みます。
イメージとしては、要素を含んだ配列と、目標となる合計値を
丸々投げて、あと宜しく!! ってするだけです。
では、solve の中を見ていきましょう。

```Partial_sum.py
# iは現在地のイメージです。
# sum は現在の数値の合計値です。
# 現在地は 0, 合計値も 0 
def solve(Nlist, target,  i=0, sum=0):
    # Nlist の長さは 5 、最初は i == 0 なので Pass!!
    if i == len(Nlist):
        return sum == target
    # あれ?! if 文の中に更に solve があります。分けわからん!!
    # もう読むのを辞めよう(笑)
    if (solve(Nlist, target, i + 1, sum)):
```

分からん、投げ出したいです(笑)。

ダメダメ!逃げちゃ。。
答えから言うと、if 文の中に再帰を設けている場合、
その再帰処理をやり切って ture or false を導きます。 
これにより if 文の中に入るか否かを判断します。
んな、馬鹿な(笑)

取りあえず出発しますか、
if の中にある solve(Nlist, target, i + 1, sum) の
先に何があるかを探す冒険に。

では、順番に行きましょう( ｀ー´)ノ

```i=0.py 
def solve(Nlist, target,  i=0, sum=0):
    #pass!
    if i == len(Nlist):
        return sum == target
    #if 文の条件文が True or False の何れか、ハッキリするまで再帰処理を続けます。
    if (solve(Nlist, target, i + 1, sum)):
        return True
```

```i=1.py
#solve(Nlist,target,1(=0+1),0) で再帰処理に入りました。
def solve(Nlist, target,  i=1, sum=0):
    #pass!!
    if i == len(Nlist):
        return sum == target
    # また再帰処理です。恐れず行きましょう!!
    if (solve(Nlist, target, i + 1, sum)):
        return True
```

```i=2.py
#solve(Nlist,target,2(=1+1),0) で再帰処理に入りました。
def solve(Nlist, target,  i=2, sum=0):
    #pass!!
    if i == len(Nlist):
        return sum == target
    # また再帰処理です。恐れず行きましょう!!
    if (solve(Nlist, target, i + 1, sum)):
        return True
```

```i=3.py
#solve(Nlist,target,3(=2+1),0) で再帰処理に入りました。
def solve(Nlist, target,  i=3, sum=0):
    #pass!!
    if i == len(Nlist):
        return sum == target
    # また再帰処理です。恐れず行きましょう!!
    if (solve(Nlist, target, i + 1, sum)):
        return True
```

```i=4.py
#solve(Nlist,target,4(=3+1),0) で再帰処理に入りました。
def solve(Nlist, target,  i=4, sum=0):
    #pass!!
    if i == len(Nlist):
        return sum == target
    # また再帰処理です。恐れず行きましょう!!
    if (solve(Nlist, target, i + 1, sum)):
        return True
```

```i=5.py
#solve(Nlist,target,5(=4+1),0) で再帰処理に入りました。
def solve(Nlist, target,  i=5, sum=0):
    #i == len(Nlist) == 5 でやっと、冒頭の if 文の中に入れます。
    if i == len(Nlist):
        # でも残念、sum(0) != target(11)。False
        return sum == target
```

なるほど、i = 5 まで行きましたが結局 False でした。
その後、どうなるんでしょう。。
とりあえず i = 5 の結果は False だったので、
前の層である i = 4 に持ち帰ってみましょう。

```i=4.py
def solve(Nlist, target,  i=4, sum=0):
    #pass!!
    if i == len(Nlist):
        return sum == target
    # if 分内の条件文は Flase でした。って事は、ここの if 文は pass です!!
    #次の if 文へ行きましょう!!
    if (solve(Nlist, target, i + 1, sum)):
        return True
    # ここでは i = 4 なので代入してみましょう
    #  (solve(Nlist, target, 4 + 1, sum + Nlist[4]))
    #  (solve(Nlist, target,   5  , 0   + 7        ) //Nlist = [1,3,5,12,7]
    if (solve(Nlist, target, i + 1, sum + Nlist[i])):
        return True
```
はい、次の if 文に移ります。
新たな条件文で、再度 i = 5 の時を確かめてみましょう。

```i=5.py
#solve(Nlist,target,5,7) で再帰処理に入りました。
def solve(Nlist, target,  i=5, sum=7):
    #i == len(Nlist) == 5 , if 文の中に入れます。
    if i == len(Nlist):
        # でも残念、sum(7) != target(11)。False
        return sum == target
```

ここまでを図にすると以下のような形になると思います。
![図2.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/5f9005b3-6bfa-7493-737d-325970cb39fe.png)
優秀な人は、頭でこれが出来るんでしょうけど、
自分はできなかったので、紙に書いたりして整理しました。
話を戻します、i = 4 までは何をしてもダメだったようです。
では、i = 3 に、この結果を報告しましょう。

```i=3.py
#solve(Nlist,target,3(=2+1),0) で再帰処理に入りました。
def solve(Nlist, target,  i=3, sum=0):
    #pass!!
    if i == len(Nlist):
        return sum == target
    #False なので pass !! 
    #今までの処理からsum が 11 になることはありませんでした
    if (solve(Nlist, target, i + 1, sum)):
        return True
    #  (solve(Nlist, target, 3 + 1, sum + Nlist[3])): //Nlist = [1,3,5,12,7]
    #  (solve(Nlist, target,   4  ,  0  +    12   )):
    #  上記の条件を以下に代入して、新たな if 分に突入!!                 
    if (solve(Nlist, target, i + 1, sum + Nlist[i])):
        return True
```

```i=4.py
#solve(Nlist,target,4(=3+1),12) で再帰処理に入りました。
def solve(Nlist, target,  i=4, sum=12):
    #pass!!
    if i == len(Nlist):
        return sum == target

    # 再帰処理です。恐れず行きましょう!!
    if (solve(Nlist, target, i + 1, sum)):
        return True
```

```i=5.py
#solve(Nlist,target,5(=4+1),12) で再帰処理に入りました。
def solve(Nlist, target,  i=5, sum=12):
    #i == len(Nlist) == 5 , if 文の中に入れます。
    if i == len(Nlist):
        # でも残念、sum(12) != target(11)。False
        return sum == target
```

False でしたね、一つ戻って報告です。

```i=4.py
#solve(Nlist,target,4(=3+1),12) で再帰処理に入りました。
def solve(Nlist, target,  i=4, sum=12):
    #pass!!
    if i == len(Nlist):
        return sum == target
    #False で Pass!
    if (solve(Nlist, target, i + 1, sum)):
        return True
    #Next↓
    if (solve(Nlist, target, i + 1, sum + Nlist[i]))://Nlist = [1,3,5,12,7]
        return True
```

```i=5.py
#solve(Nlist,target,5(=4+1),12 + 7) で再帰処理に入りました。
def solve(Nlist, target,  i=5, sum=19):
    #i == len(Nlist) == 5 , if 文の中に入れます。
    if i == len(Nlist):
        # でも残念、sum(19) != target(11)。False
        return sum == target
```

図にしてみます。
![図3.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/4cedd8af-a0dd-9db8-3876-ce895facc79b.png)
なんか、木構造見たいです(笑)
気の長い作業ですが、以下のポイントだけ抑えれば oK です。


**1.True, False が見えるまで if 文の条件文(再帰)は追っかけ続ける
2.True, False が見えたら、ひとつ前の層に戻り、solve 内の記述に沿い忠実に動作を追いかける**

偉そうに書いていますが、私は全く知らなかったので、
何をどう遷移しているか確認するために
以下のように pirnt を混ぜました。

```Partial_sum.py
def solve(Nlist, target,  i=0, sum=0):
    print(f"i:{i},sum:{sum}") # 再帰処理中に、現在値を表示して分かりやすくする
    if i == len(Nlist):
        # 再帰処理は、冒頭に最下層に来た時の条件文を入れます。
        # なので、この if 文に入った時が最下層と分かるコメントを print します
        print(f"Result:i={i},sum={sum}") 
        print() # 次の処理とを区切るために改行しています
        return sum == target
    if (solve(Nlist, target, i + 1, sum)):
        return True
    if (solve(Nlist, target, i + 1, sum + Nlist[i])):
        return True
    return False

Nlist = [1,3,5,12,7]
target = 11
print(solve(Nlist, target))
```

実行結果を見てみましょう!!

```実行結果.py
i:0,sum:0
i:1,sum:0
i:2,sum:0
i:3,sum:0
i:4,sum:0
i:5,sum:0
Result:i=5,sum=0
#↑前述の図と比較してみてください。i, sum の変化が図と一致していません？
#Result:i=5,sum=0 とあるように sum は 11 ではないので False を返します
#返した後は i=4 の時に帰ります。
#帰ったあとは、そのまま次の IF 文に続きます。
#よって、次の表示は以下にある i = 5 の時の pirnt になります。
#理解できない人は前述のページに戻ってください。
i:5,sum:7
Result:i=5,sum=7
#↑sum(=7) != 11 なので False です。
#よって、i = 4 の時の 2 つの if 文は両方とも False となります。
#次は i = 3 の時の if 文に戻りますが、処理は後は前述と同じです。
i:4,sum:12
i:5,sum:12
Result:i=5,sum=12

i:5,sum:19
Result:i=5,sum=19

i:3,sum:5
i:4,sum:5
i:5,sum:5
Result:i=5,sum=5

i:5,sum:12
Result:i=5,sum=12

i:4,sum:17
i:5,sum:17
Result:i=5,sum=17

i:5,sum:24
Result:i=5,sum=24

i:2,sum:3
i:3,sum:3
i:4,sum:3
i:5,sum:3
Result:i=5,sum=3

i:5,sum:10
Result:i=5,sum=10

i:4,sum:15
i:5,sum:15
Result:i=5,sum=15

i:5,sum:22
Result:i=5,sum=22

i:3,sum:8
i:4,sum:8
i:5,sum:8
Result:i=5,sum=8

i:5,sum:15
Result:i=5,sum=15

i:4,sum:20
i:5,sum:20
Result:i=5,sum=20

i:5,sum:27
Result:i=5,sum=27

i:1,sum:1
i:2,sum:1
i:3,sum:1
i:4,sum:1
i:5,sum:1
Result:i=5,sum=1

i:5,sum:8
Result:i=5,sum=8

i:4,sum:13
i:5,sum:13
Result:i=5,sum=13

i:5,sum:20
Result:i=5,sum=20

i:3,sum:6
i:4,sum:6
i:5,sum:6
Result:i=5,sum=6

i:5,sum:13
Result:i=5,sum=13

i:4,sum:18
i:5,sum:18
Result:i=5,sum=18

i:5,sum:25
Result:i=5,sum=25

i:2,sum:4
i:3,sum:4
i:4,sum:4
i:5,sum:4
Result:i=5,sum=4

i:5,sum:11
Result:i=5,sum=11

True
```

以上のように、遷移できない限界まで達した後に、
一つ戻り、また限界まで動作するような処理を繰り返す手法を**深さ優先探索**と言います。
資料には、比較的簡単に書けるって書いてありますが、
いやいや、初心者にはキッツイ!!( ﾟДﾟ)

まだまだ先は長そうです(*´ω｀)