递归出口如何设计啊?

举个简单的例子,有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

相关推荐

02-01 12:05
复旦大学 Java
腾讯的提前批大概率应该是没有笔试的,但是这个时候有相当部分的同学简历估计都没有准备好,没准备好的同学也不用急,大部分都是3月之后开,这个时候开的绝大多数都是神仙打架,问的东西也比较难,打算投递的同学也多看下计算机网络和操作系统,腾讯对这部分的知识问的比较多。另外多刷下牛客的热门题库,刷题注意刷ACM模式,和牛客的周赛题,腾讯有的部门会从这里面出原题。我是@程序员花海关注我,带你了解更多校招资讯!
程序员花海:还没有来得及准备的同学可以看下学习路线:https://www.nowcoder.com/discuss/824693499982315520?sourceSSR=users算法题:https://www.nowcoder.com/feed/main/detail/20e7a999fa04485b88340a274411ca0d?sourceSSR=users八股文:https://www.nowcoder.com/discuss/833102362771251200?sourceSSR=users简历书写方式:https://www.nowcoder.com/discuss/839907820706205696?sourceSSR=users都是以前在牛客发的文章~
软开人,秋招你打算投哪些...
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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