部分和問題

部分和問題

深さ優先探索では、一番はじめの状態から遷移を繰り返すことで 全ての状態 を生成します。

したがって、すべての状態に対して操作 を施したり、全状態を列挙 することが可能です。

[問題]

整数が n個 与えられます。

その中からいくつか選び、その和をちょうど k にすることができるか判定してください。

[条件]

・整数の個数 n は、1以上20以下
・各整数の値は、-100000000以上100000000以下
・目標とする数値（部分和） k は、-100000000以上100000000以下

[解き方]
各整数を１つ目から順番に加えるかどうかを決めていき、n個すべてについて決め終わったら、その和が k に等しいかどうかを判定します。

再帰関数を使用します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# ------------ 入力例１ ----------
lst = [1, 2, 4, 7]    # 各要素
k = 13                # 目標とする数値（部分和）
# ------------ 入力例２ ----------
# lst = [1, 2, 4, 7]  # 各要素
# k = 15              # 目標とする数値（部分和）
# --------------------------------
def dfs(i, total):
    print(i,total)
    if i == len(lst):       # 全部決め終わった場合
        return total == k   # 今までの和が[目標とする数値]と等しいかどうかを返す
    
    if dfs(i + 1, total):   # lst[i]を使わない場合
        return True
    
    if dfs(i + 1, total + lst[i]):  # lst[i]を使う場合
        return True

    # lst[i]を使うか使わないかにかかわらず[目標とする数値]がつくれないので False を返す
    return False

if dfs(0, 0):
    print('Yes')
else:
    print('No')

[実行結果（入力例1）]

Yes

2 + 4 + 7 を足し合わせると 13 になるので Yes が解となります。

[実行結果（入力例2）]

No

どんな組み合わせを行っても 15 となることはないので No が解となります。