hzCPPOJ

数据结构_图_和

时间限制:  1 s      内存限制:   128 MB
提交:42     正确:8     分值:98

题目描述

现给定一个含有n个元素的数组A,要求:从这n个数中选择一些数,这些数的和恰好为k。如果能够达到目的,输出”Of course,I can!”; 否则输出”Sorry,I can’t!”.

输入

第一行为n(1<=n<=20) 第二行为n个整数,每个数的范围为(-10^5≤A[i]≤10^5) 第三行为整数k(-10^8≤k≤10^8) 。

输出

如果能够达到目的,输出”Of course,I can!”; 否则输出”Sorry,I can’t!”.

样例

样例输入:
4 1 2 4 7 13
样例输出:
Of course,I can!

提示

DFS来解这道题。
假如n = 4,目标值k = 13,4个数分别为1 2 4 7则:
①我们选1,1 < 13,继续选;
②我们选1 2,1+2 <13,继续选;
③我们选1 2 4,1+2+4 < 13,继续选;
④我们选1 2 4 7,1+2+4+7 > 13,7不选;
其实‚中的2我们也可以不选,直接往下选,那就变成
我们选1 4 ,2不选,1+4 < 13,继续选;
⑤我们选1 4 7,2不选,1+4+7 < 13
⑥同样的,①中我们可以不选1,则:
我们选2,不选1,2 < 13,继续选;
我们选2 4,不选1,2+4 < 13,继续选;
我们选2 4 7,不选1,2+4+7 = 13 结束。

提交人

AmberXie