现给定一个含有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!”.
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 结束。