hzCPPOJ

3153-用递归法求“几个数之和”

时间限制:  1 s      内存限制:   128 MB
提交:199     正确:102     分值:86

题目描述

已知一个一维正数组A[1..n](n<50)。又已知一个正整数M。如果能使数组A中任意几个元素之和等于M,则输出YES,反之输出NO。

输入

第一行为N,M。N表示数组元素个数,M表示需要比较的整数M。

第二行为数组A。

输出

YES或者NO

样例

样例输入:
3 15 5 5 5
样例输出:
YES
样例输入:
4 15 4 5 5 1
样例输出:
YES
样例输入:
3 15 4 5 5
样例输出:
NO

提示

题目意思是判断能否从数组A[1..n]取任意几个数使其和为m
对于A[1..n]中任意元素A[n]只有取或者不取两种情况:
1.取A[n]
问题转化为:对于一个确定的数组A[1..n-1]和一个确定的数m-A[n],判断能否使数组A[1..n-1]中任意几个元素的和为m-A[n]
2.不取A[n]
问题转化为:对于一个已确定的数组A[1..n]和一个确定的数m,判断能否使数组A[1..n-1]中任意几个元素之和为m。

提交人

AmberXie

来源/分类