取组合数问题

需求：

现有一个数组[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;
  }
}

复制