递归出口如何设计啊?

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

相关推荐

object3:开始给部分🌸孝子上人生第一课了
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务