c++递归算法1到n的组合数_0x02|递推与递归 排列组合题型合集

概念回顾

排列组合问题是算法中比较常见的问题，这种题型的难点在于组合的数据量通常比较大，朴素写法的复杂度往往达到指数级别，一般都需要优化处理。看题之前，我们先来回顾一下排列和组合的定义。

排列的英文是Permutation，简称P，组合的英文是Combination，简称C。

排列是指从n个数中按顺序选出k个，有多少种可能。

组合是指从n个数中选出k个，有多少种可能。

显然，P和C的区别在于是否有顺序。

P的公式是：

是全排列，是先排k个数后的全排列。

C的公式是：

注意分母多了一个，这正是顺序的排列数，组合不需要顺序，除去。

复习完毕，来看题。

92. 递归实现指数型枚举

题目：从 1~n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。

比如n=3，也就是从1到3这3个数种选择任意的数量，选择1个、选择2个、选择3个这3种情况。

这个不要求顺序，比如选择1和2，和选择2和1是一样的。

那么答案就是

这里

显然，我们可以用位来表示数字是否选取。那么每一个位都可能选择或者不选择，比如n=3的情况，那么所求即是从000到111所有可能的值，也就是2的3次方种情况。那么我们直接输出0到的数值位1的位置不就能够达到目的了吗？

#include #include using namespace std;int n;int main(){    cin >> n;    for(int i = 0; i 1 <        for(int j = 0; j 15; j++) {            if(i >> j & 1) {                printf("%d ", j + 1);            }        }        printf("\n");    }    return 0;}

这是非递归的做法，还有一种递归的做法，从0开始，每次前进一位，处理选择和不选择两个分支，其实就是一棵树，做法如下，这也是闫总视频中的解法。

#include using namespace std;int n;// u是当前枚举到的数，state是二进制数记录哪些数被选void dfs(int u, int state) {    if (u == n) {        for (int i = 0; i             if (state >> i & 1)                cout <1 <" ";            cout <endl;        return;    }    dfs (u + 1, state);  // 不用u这个数    dfs (u + 1, state | (1 <// 用u这个数}int main() {    cin >> n;    dfs(0, 0);    return 0;}

递归重要的是对分支的处理，由于使用位保存，不需要恢复现场，如果是使用一个数组来存储，那么需要恢复现场。

再来看下一题。

93. 递归实现组合型枚举

题目：从 1~n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。

这一题更简单，上一题我们解决了随机选择任意个，其实已经包含了m个这个数字，所以只需要限定一下数量然后输出就可以了。

还是用3举例子，比如从3个中选择2个，那么也就是state二进制表示中存在2个1，统计一下1的个数。

然而这一题要求顺序输出结果，这个要求对于非递归的实现造成了致命打击，因为92题中非递归的做法会导致结果不是顺序的，那么怎么办呢？

acwing上有个童鞋骨骼清奇，发现了一个规律，如果用0来标记选择，刚好满足顺序！

1.我们来看样例 5 3结果是1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5 有什么规律呢？我们来一个1到(1<<5)-15 3    1--00001    2--00010    3--000111 2 3    4--00100    5--001011 2 4    6--001101 2 5    7--00111    8--01000    9--010011 3 4   10--010101 3 5   11--01011   12--011001 4 5   13--01101   14--01110   15--01111   16--10000   17--100012 3 4   18--100102 3 5   19--10011   20--101002 4 5   21--10101   22--10110   23--10111   24--110003 4 5   25--11001   26--11010   27--11011   28--11100   29--11101   30--11110   31--11111我们可以发现0出现的位置和我们要求的数列有关！！！

非递归的写法如下，先反转0和1，然后还是统计1的数量，轻松解之。非递归的做法看起来非常巧合，再仔细考虑一下就会发现，其实不是巧合，而是必然！

在二进制位中，从0到n的值，0总是从左边开始占据位置，1总是从右边开始占据位置，这种说法虽然有点感性，但确实是这样的，对于n个数选择m个，因为0和1是对称的，假设m个0一开始在最左边，那么必然是最右边的一个0开始往右移动，只有第一个0移到了最右边，才会开始移动第二个0，依次类推，最终出现了顺序的现象。

#include #include using namespace std;int n, m;int main(){    cin >> n >>m;    int max = (1<-1;for(int i=0; i<1 <        int k = 0;int x = max ^ i;for(int j=0; j            if(x >> j & 1){                k++;            }        }if(k == m){for(int j=n-1; j>=0; j--){if(x >> j & 1){printf("%d ", (n-j));                }            }printf("\n");        }    }return 0;}

递归解法，在92题的函数上稍有改动就可以了，递归解法理解起来更加自然，可以很好的加强对递归的理解。

#include using namespace std;int n, m;void dfs(int u, int sum, int state){    if(sum+n-u         return;    }        if(m == sum){        for(int i=0; i            if(state >> i & 1){                cout<1<<" ";            }        }cout <endl;return;    }if(n == u){return;    }    dfs(u+1, sum+1, state | 1<    dfs(u+1, sum, state);}int main(){cin>>n>>m;    dfs(0, 0, 0);return 0;}

再来看看最后一题，搞完就收工了，坚持。

94. 递归实现排列型枚举

题目：把 1~n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。

这个就是全排列，有顺序的，排列。

还是n=3，那么可能的顺序：

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

第一位有3种可能，第二位有2种可能，第三位有1种可能，也就是种排列。

我们可以用111表示初始状态，每选择一个，就将其设置位0。非递归的做法可以考虑用队列来处理，递归的做法都可以用队列转换为非递归。我们还有另外一种选择，C++的标准库，std::next_permutation函数可以非常方便的实现全排列，如下：

#include using namespace std;const int N=11;int n,a[N];int main() {    scanf("%d",&n);    for(int i=1;i<=n;i++)        a[i]=i;    do    {        for(int i=1;i<=n;i++)            cout<" ";cout<<endl;    }while(next_permutation(a+1,a+1+n));return 0;}

是不是超级方便，全排列全部交给STL标准库，都不用动脑筋。

用递归的方式来做需要维护一个数组，这个数组主要是记住已经选择的数字，最终需要输出这个数组。如下所示：

#include #include using namespace std;vector<int> path;int n;void dfs(int u, int state){    if(u == n){        for(auto x : path)            cout<1<<" ";cout<<endl;return;    }for(int i=0; i        if(!(state >> i & 1)){            path.push_back(i);            dfs(u+1, state | (1 <            path.pop_back();        }    }}

全排列每次都需要遍历所有的数字，找到可以占位的位置，然后记录这个位置，每次进入一个分支，处理完后都需要恢复现场，保证每个分支进去都是正确的数据，递归调用引用全局数据会污染这个全局数据，也就是树的前序遍历，一直走到叶子节点后才使用这个污染的全局数据进行输出，既然是污染的数据，走到叶子节点后，就要开始清理现场，把自己这条线上的污染都清理掉，最终回到根节点的时候一切完好如初。

总结

这是3道基础的排列组合题，重在理解递归与非递归的区别，同时回顾一下排列与组合的区别，特别的，还需要注意顺序问题，看起来巧合的数据，换个角度又很简单。C++标准库提供了全排列的函数，可以直接使用，全排列需要记录路径(选择了哪一个)，不像组合只关心某个位是否选择，所以排列问题会麻烦一些。

全排列还可以增加一题：把 1~n 这 n 个整数选出m个数排成一行后随机打乱顺序，输出所有可能的次序。

通过上面几个题目，如果能让你对排列组合和递归有更深的理解，那就给我点个赞吧！更多的赞会让我更有动力更用心的写更详细的题解！

温馨提示

如果你喜欢本文，请分享到朋友圈，想要获得更多信息，请关注ACM算法日常。

点赞的时候，请宠溺一点