给你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
- 《挑战程序设计》P30