递归出口如何设计啊?

举个简单的例子,有n个数,从中选出若干个使得他们的和恰好为m,求总的方法数
比如数据是1,5,2,3,4求和是4的个数, 4 =4, 4=1+3总共两种
设f(n,m)表示从数列1-n中选出若干个数和是m的个数
那么f(n,m) = f(n-1,m-datas[n])+f(n-1,m);这个递推很好写,包括datas[n]和不包括datas[n]两种。
可是递归出口该怎么设计,下面图片是我慢慢琢磨的,对不对也不知道。想请教下对于一般的递推公式如何设计递归出口,这是二维的,如果三维呢
或者更高维呢

全部评论
public class sumCnt { public static void main(String[] args){ int[] a = {1, 2, 4, 3, 5}; System.out.println(f(a.length - 1, 4, a)); } // n: 遍历数组a下标,从0到a.length-1; public static int f(int n, int m, int[] a){ if(n == 0){ return a[n] == m ? 1: 0; } if(a[n] == m){ return f(n-1, m, a) + 1; }else if(a[n] < m){ return f(n-1, m, a) + f(n-1, m - a[n], a); }else{ return f(n-1, m, a); } } } 仅供参考哈!
点赞 回复 分享
发布于 2017-04-08 11:45

相关推荐

昨天 22:05
已编辑
门头沟学院 Web前端
我是2月23号开始投简历的,投出去基本没回应,到现在只有3场面试,之前已经错过了秋招,所以想争取春招冲一冲;我想请牛友们,各位佬,看看我的简历,春招可以冲中小厂吗?2月底投出去的简历基本直接被拒,惨~目前我的进度是八股文看了很多,刷了30+算法题(弱爆啦),场景题基本没碰可能会G,常见手撕题敲了一遍(记不住,大概率G);项目很可能经不住深度拷打,还在加强学习。如果屏幕前的牛友们愿意给出建议,请畅所欲言,我一定认真阅读。毕设也欢迎各位佬直接开喷,链接:https://github.com/bignosecss/reverse-roadmap---一周过去了,更新下这周的春招的投递情况吧。这周总共约了4场面试,都是小公司;面试八股很少,没有手撕和算法,问场景和项目里的细节比较多。一家面了之后没消息了,一家二面挂,另外两家面试体验非常棒,面试官还会解答没答上的问题,总体来说反馈比2月份多不少,要简历的也多了。在招聘网站上投了很多,大多未读和已读不回,或者要了简历不回复的。邮箱、官网的投递基本没有声响,大海里扔石头,没声儿。。。感觉今年春招真的很难了,投出去没有水花,有力气没处使;不管是小厂中厂,投出去大多没回应,倒是很多外包找。不知道大问题在哪,感觉简历写的也差不多,不知道怎么继续优化了。总之每天保持学习节奏,不停的投,坚持到春招结束,相信会有机会的!
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务