部分和問題のif文の中身が何をしているのかわからない

Question

部分和問題のif文の中身が何をしているのかわからないです。
http://y0m0r.hateblo.jp/entry/20121203/1354549288
を参考に部分和問題を書いたら

# coding=utf-8
# 部分和問題
# 深さ優先検索

# 整数がn個与えられる。その中からいくつか選び、その環をちょうどkにすることができるかどうかを判定する

def solve(integer_list, target_sum,  i=0, sum=0):
    if i == len(integer_list):
        return sum == target_sum
    if (solve(integer_list, target_sum, i + 1, sum)):
        return True
    if (solve(integer_list, target_sum, i + 1, sum + integer_list[i])):
        return True
    return False

# n個の整数
integer_list = [1,3,5,12,7]
# k
target_sum = 11

print(solve(integer_list, target_sum))
# => True

のようになったのですが、
この

    if (solve(integer_list, target_sum, i + 1, sum)):
        return True
    if (solve(integer_list, target_sum, i + 1, sum + integer_list[i])):
        return True

の中のif文の条件が何をしているのかわかりません。

if (solve(integer_list, target_sum, i + 1, sum)):

if (solve(integer_list, target_sum, i + 1, sum + integer_list[i])):

は何の機能なのでしょうか？

Answer 1

再帰処理ですね。
solveの引数は、次のように解釈するといいかと思います。

• integer_list

文字通り、整数のリスト。途中変更されることはない。([1,3,5,12,7])

• target_sum

文字通り、対象となる和。途中変更されることはない。(11)

• i

どこまでリストを見たか記憶している変数。

• sum

これまでの和。

さらに、それぞれのif文は、次を意味します。

• if i = len(integer_list): 終了条件

リストの全てをチェックした場合、現段階の合計がtarget_sumと等しければTrueを返す。
異なる場合はFalseを返す。

• if (solve(integer_list, target_sum, i + 1, sum)):

今着目している数値(integer_list[i])を足さずに、次の数値に着目する。

• if (solve(integer_list, target_sum, i + 1, sum + integer_list[i])):

今着目している数値(integer_list[i])を足して、次の数値に着目する。

---

これらを把握したうえで、プログラムの処理を追ってみましょう。
solve([1,3,5,12,7], 11, 0, 0)が呼ばれると、次の二パターンに分割して問題を解決します。
0. 0番目の数値をsumに足す場合
次のようにsolveを呼び出し、判断を次のsolveに委託します。solve([1,3,5,12,7], 11, 1, 1)
0. 0番目の数値をsumに足さない場合
次のようにsolveを呼び出し、判断を次のsolveに委託します。solve([1,3,5,12,7], 11, 1, 0)

... どんどん二分割されていきます ...

これをある程度続けていくと、いつかリストの最後まで見ることになります。
その時の条件が、i == len(integer_list)です。
例えばsolve([1,3,5,12,7], 11, 5, 11)が呼ばれると、終了条件に達します。

リスト長がこの場合5ですから、2の5乗で32パターンに分割されますが、
それぞれが必ず終了条件に達し、結論がTrue/Falseで返されます。

---

私も初めて再帰処理を見たとき、狐に化かされたような気がしました。
面倒でも、ひとつひとつ紙に書いてみると、感覚がつかめるかもしれません。

Comments

[退会済みユーザー]

ありがとうございます。
if (solve(integer_list, target_sum, i + 1, sum)):
return True
if (solve(integer_list, target_sum, i + 1, sum + integer_list[i])):
return True
で２つのif文の sum　の値の保存はどこで行われているのでしょうか？ i + 1でiがどんどん増えていく理由はわかるのですが。

[退会済みユーザー]

また、2つのif文のreturn True　で一度２つのif文が呼ばれればsolveメソッドはTrueを返すと思ったのですが、それは違うのでしょうか？（なら必ずこのメソッドはTrueを返すような気がしたのですが...）

[LouiS0616]

sumの値は保存されません。毎度毎度引数として渡されます。
実際に紙に書いてみると、sumの値を変数に保存しなくても済む感覚が掴めるかと思います。

[LouiS0616]

> ２つのif文のreturn trueで...
ちょっと待ってください。Trueが返されるのは、if文の条件が真のときのみです。
そういう意味で、『判断を次のsolveに委託します』という表現を使いました。

全てのif文の条件がFalseとなったとき、solve関数最終行に到達し、solveはFalseを返します。

Answer 2

単純に自身を呼び出しているだけです。
最終的にiとinteger_listの長さが同じになるのでbool値がreturnされます。結果として条件文の判定として使われています。

再帰関数について調べてみると良いです。