部分和問題

gistfile1.py

def dfs(i, sum, a, k):

  if i == len(a):
    return sum == k

  if dfs(i+1, sum, a, k):
    return True

  if dfs(i+1, sum+a[i], a, k):
    return True

  return False

def solve(a, k):
  if dfs(0, 0, a, k):
    print "Yes"
  else:
    print "No"

solve([1, 2, 4, 7], 13)
solve([1, 2, 4, 7], 15)