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 <iostream>
#include <math.h>
using namespace std;
int n;
int main()
{
cin >> n;
for(int i = 0; i < 1 << n; i++) {
for(int j = 0; j < 15; j++) {
if(i >> j & 1) {
printf("%d ", j + 1);
}
}
printf("\n");
}
return 0;
}
这是非递归的做法，还有一种递归的做法，从0开始，每次前进一位，处理选择和不选择两个分支，其实就是一棵树，做法如下，这也是闫总视频中的解法。
#include <iostream>
using namespace std;
int n;
// u是当前枚举到的数，state是二进制数记录哪些数被选
void dfs(int u, int state) {
if (u == n) {
for (int i = 0; i < n; i ++)
if (state >> i & 1)
cout << i + 1 << " ";
cout << endl;
return;
}
dfs (u + 1, state); // 不用u这个数
dfs (u + 1, state | (1 << u)); // 用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)-1
5 3
1--00001
2--00010
3--00011
1 2 3
4--00100
5--00101
1 2 4
6--00110
1 2 5
7--00111
8--01000
9--01001
1 3 4
10--01010
1 3 5
11--01011
12--01100
1 4 5
13--01101
14--01110
15--01111
16--10000
17--10001
2 3 4
18--10010
2 3 5
19--10011
20--10100
2 4 5
21--10101
22--10110
23--10111
24--11000
3 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 <iostream>
#include <math.h>
using namespace std;
int n, m;
int main()
{
cin >> n >>m;
int max = (1<<n)-1;
for(int i=0; i<1 << n; i++){
int k = 0;
int x = max ^ i;
for(int j=0; j<n; 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 <iostream>
using namespace std;
int n, m;
void dfs(int u, int sum, int state)
{
if(sum+n-u < m){
return;
}
if(m == sum){
for(int i=0; i<n; i++){
if(state >> i & 1){
cout<<i+1<<" ";
}
}
cout << endl;
return;
}
if(n == u){
return;
}
dfs(u+1, sum+1, state | 1<<u);
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 <bits/stdc++.h>
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<<a[i]<<" ";
cout<<endl;
}while(next_permutation(a+1,a+1+n));
return 0;
}
是不是超级方便，全排列全部交给STL标准库，都不用动脑筋。
用递归的方式来做需要维护一个数组，这个数组主要是记住已经选择的数字，最终需要输出这个数组。如下所示：
#include <iostream>
#include <vector>
using namespace std;
vector<int> path;
int n;
void dfs(int u, int state)
{
if(u == n){
for(auto x : path)
cout<<x+1<<" ";
cout<<endl;
return;
}
for(int i=0; i<n; i++){
if(!(state >> i & 1)){
path.push_back(i);
dfs(u+1, state | (1 << i));
path.pop_back();
}
}
}
全排列每次都需要遍历所有的数字，找到可以占位的位置，然后记录这个位置，每次进入一个分支，处理完后都需要恢复现场，保证每个分支进去都是正确的数据，递归调用引用全局数据会污染这个全局数据，也就是树的前序遍历，一直走到叶子节点后才使用这个污染的全局数据进行输出，既然是污染的数据，走到叶子节点后，就要开始清理现场，把自己这条线上的污染都清理掉，最终回到根节点的时候一切完好如初。
总结
这是3道基础的排列组合题，重在理解递归与非递归的区别，同时回顾一下排列与组合的区别，特别的，还需要注意顺序问题，看起来巧合的数据，换个角度又很简单。C++标准库提供了全排列的函数，可以直接使用，全排列需要记录路径（选择了哪一个），不像组合只关心某个位是否选择，所以排列问题会麻烦一些。
全排列还可以增加一题：把 1~n 这 n 个整数选出m个数排成一行后随机打乱顺序，输出所有可能的次序。
通过上面几个题目，如果能让你对排列组合和递归有更深的理解，那就给我点个赞吧！更多的赞会让我更有动力更用心的写更详细的题解！
腾讯云开发者
