6.2 全探索をPythonで解いてみた

問題

総当たり
長さ n の数列 A と整数 m に対して、A の要素の中のいくつかの要素を足しあわせて m が作れるかどうかを判定するプログラムを作成してください。A の各要素は１度だけ使うことができます。
数列 A が与えられたうえで、質問として q 個の m_i が与えれるので、それぞれについて "yes" または "no" と出力してください。

入力
１行目に n、２行目に A を表す n 個の整数、３行目に q、４行目に q 個の整数 miが与えられます。

出力
各質問について A の要素を足しあわせて m_i を作ることができれば yes と、できなければ no と出力してください。

制約
n≤20
q≤200
1≤Aの要素≤2,000
1≤mi≤2,000

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_A&lang=ja

解法

def solve(i, target):
    global input_list
    if target == 0:
        return True
    if i >= len(input_list):
        return False
    res = solve(i + 1, target) or solve(i + 1, target - input_list[i])
    return res


target = 5
input_list = [1, 5, 7, 10, 21]
solve(0, target)

target = 4
input_list = [2, 4, 17, 8]
solve(0, target)

target = 25
input_list = [2, 4, 17, 8]
solve(0, target)

solve(i,target)を「input配列のi番目以降の要素を使ってtargetを作れる場合Trueを返却する」メソッドとした場合、今回の問題設定では、solve(0,target)がTrueになるかどうかを調べることが課題となる。

そのため、まずsolve(0,target)を部分問題に分割し、solve(i+1,target)とsolve(i+1,target - input配列[i])のどちらかがTrueであれば、Trueが返却されるとする。
iをどんどん増やしていき、どこかのプロセスの分岐でtarget - input配列[i]=0となれば、返却値はTrueになり、targetを満たす組み合わせがあることがわかる。