PCC-34a : 部分和問題

プログラミングコンテストチャレンジブック python アルゴリズム

本ソースコードは、DFS:Depth-First Serach（深さ探索優先）を用いた例題となります。

pcc-34a.py

#!/usr/bin/python
# -*- coding:utf-8 -*-

# input
n, k = map(int, raw_input().split())
a = list(map(int,raw_input().split()))


# func
def dfs(i,sum):
    if i == n : return k == sum

    # a[i]を使用しない
    if dfs(i + 1, sum) : return True

    # a[i]を使用する
    if dfs(i + 1, sum + a[i]): return True

    # a[i]を使用しても使用しなくてもkが導出できない
    return False

# solve
if dfs(0,0) : 
    print "Yes\n"
else :
    print "No\n"

pcc-34a.py 直

システムテスト：

$ python pcc-34a.py < pcc-34a_input1.txt 
Yes

# 以下実際のinputとoutputを記載しています。
input : 
    n=4
    k=13
    a={1,2,4,7}
output:
    Yes

pcc-34a_input1.txt 直

$ python pcc-34a.py < pcc-34a_input2.txt 
No

# 以下実際のinputとoutputを記載しています。
input : 
    n=4
    k=15
    a={1,2,4,7}
output:
    No

pcc-34a_input2.txt 直