给你n个数(a1,a2,a3…….an) ,是否存在某一些数字加起来等于k,有就输出 “YES”,否则输出 “NO”。

  • 数据范围：n<20;
  • a1+a2+….an在int范围里面.

输入

多组输入
每组第一行输入两个数n,k
第二行输入n个数a1 a2 ...... an

输出

如果存在一些数加起来为k输出"YES";否则输出"NO".

样例输入

5 6
2 3 5 2 1
3 6
2 3 9

样例输出

YES
NO

Solutions

　　使用深度优先，主要是状态转移的过程要搞清楚。

class Solution(object):
	def if_sum(self, arr, k):
		n = len(arr)
		def dfs(i, sum):
			"""DFS: 已经从前 i 项得到了和 sum，然后对 i 项之后进行分支"""
			# 如果前 n 项都计算过了，则返回 sum 是否与 k 相等
			if i == n:
				return sum == k

			# 不加上当前的 a[i] 的情况
			if dfs(i+1, sum):
				return True

			# 加上当前的 a[i] 的情况
			if dfs(i+1, sum + arr[i]):
				return True

			return False
		return dfs(0, 0)

s = Solution()
print(s.if_sum([1, 2, 4, 7], 15))

References

  1. 《挑战程序设计》P30