首页 > 代码库 > 组合 最详细的解题报告
组合 最详细的解题报告
题目大意:已知一个数组array,长度为m,计算其中任意n个数的组合
解题思路:分析m=5,n=3时的10组组合数:
1、首先固定下标为m-1(最后一个)的数,其前面就是m-1,n-1的组合数,共6个组合;
2、其次固定下标为m-2(倒数第二个)的数,其前面就是m-2,n-2的组合数,共3个组合;
3、以此类推。一般的:m个数中n个数组合递推到“m-1个数中n-1个数的组合,m-2个数中n-1个数的组合,......, n-1个数中n-1个数的组合”,共m-n+1次递归
4、递归结束的条件是:r<=0
具体算法(java版)
1 public static int[] ans; //用来存储每次计算出来的结果 2 3 // 输出array数组中的数据 4 public static void output(int[] array) { 5 for (int i = 0; i < array.length; i++) { 6 System.out.print(array[i] + "\t"); 7 } 8 System.out.println(); 9 }10 11 public static void comb(int[] array, int m, int n) {12 if (n > 0) {13 for (int i = m; i >= n; i--) {14 ans[n - 1] = array[i - 1];15 comb(array, i - 1, n - 1);16 }17 } else {18 output(ans);19 }20 }21 22 public static void main(String[] args) {23 int[] array = { 1, 2, 3, 4, 5}; // 待组合的元素24 int m = 5;25 int n = 3;26 ans = new int[n];27 comb(array, m, n);28 }
组合 最详细的解题报告
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。