取组合数问题
需求：
现有一个数组[1,2,3,4……]。里面数字是任意的不重复的。现在要从里面取出N个数字组成一组，导出这些数组。
思路：
这是一个数学上的组合数问题。网上有一些算法可以求出组合数的数量，但现在需要把每一个组合数取出来。首先考虑到必须得用到递归，具体如何取能防止出现重复组合，就比较巧妙了，如果用判断重复不仅low，而且会有非常繁重的计算量，最好就是循环的时候能避开重复组合的问题。
小学里面学过如何数线段个数，或者某种三角形的个数，老师会使用一种方法，比如以第一个端点为准，找到所有线段，再以第二个端点开始找，并且不回头找，因为会重复，这就是典型的组合数，只是N取2的组合。受此启发，可以设计出递归的寻找M取N个组合数。
Iterable<List<int>> comboNum(List<int> m, int n) sync* {
if (n == 1) {
yield* m.map((y) => [y]);
} else {
for (int i = 0; i < m.length - n + 1; i++) {
for (var sub in comboNum(m.sublist(i + 1), n - 1)) {
yield sub..add(m[i]);
}
}
}
}代码解读：
如果取1个数，则返回单个元素的数组，跳出递归
否则，我们循环遍历数组，但不遍历到最后若干个元素，因为需要留足组合数的其他元素。
然后我们递归找到取n-1的所有组合，再把当前元素结合进去就可以了。
==============================
补充，稍作修改后，可以获得组合数的个数
int comboNumCount(int m, int n) {
if (n == 1) {
return m;
} else {
int j = 0;
for (int i = 0; i < m - n + 1; i++) {
j += comboNumCount(m - i - 1, n - 1);
}
return j;
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019-03-15，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
