算法学习系列（四）：指数型枚举、全排列、组合型枚举

本文主要是介绍算法学习系列（四）：指数型枚举、全排列、组合型枚举，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

引言

本篇其实也是递归的一部分，主要还是使用递归的方式去做，然后关于这个枚举啊，好像今年的美团笔试题就出的是全排列的问题，在整个四道笔试题中在第三个位置，难度也算是中等了，而且关于这个指数型枚举在算法竞赛中，很多地方也会用到该思想，所以说这方面的问题还是比较重要了，然后的话写的可能比较干吧，因为写这个主要是为了给自己看的，也是为了帮助自己总结，忘了的时候看看，其次也是为了给面试加分的，所以我也不会去教学啥的，废话不多说直接开干。

一、指数型枚举

指数型枚举：给一个数n，要求输出1~n所有可能的结果, 
eg:n == 3 //空集
3
2
2 3
1
1 3
1 2
1 2 3

1.递归写法

#include <iostream>using namespace std;const int N = 20;  //这里题目告诉n <= 15
bool st[N];  //false代表不选 true代表选
int n;void dfs(int u)  //u代表当前的值
{if(u > n)  //若u超过了n就根据st输出{for(int i = 1; i <= n; ++i){if(st[i]) cout << i << " ";}puts("");  //就是回车return;}st[u] = false;  //当前的值不选dfs(u + 1);st[u] = true;  //当前的值选dfs(u + 1);
}int main()
{cin >> n;dfs(1);return 0;
}

2.位运算写法

该写法相当于是拿位运算来充当st的，比如n==3的话，那么就有3位，000，代表123都不选，001代表第一位选，101代表第一位和第三位选，然后从0~2^3刚好包含了所有的情况，1<<n就是2 ^ n，再之后判断每一位是否为1就行了，用k >> i & 1就可以知道了

#include <iostream>using namespace std;int main()
{int n;cin >> n;for(int k = 0; k < 1 << n; ++k)  //k为一种情况，有2^n种情况（一个数选or不选）{for(int i = 0; i < n; ++i)  //总共有n位{if(k >> i & 1)  //代表数k的第i位是否为1{cout << i + 1 << " ";}}puts("");  }return 0;
}

二、全排列

全排列跟指数型枚举不同的是，指数型枚举是该位要么选要么不选，而全排列是该位选哪一个数

1.写法一：使用ways数组来存

该方法是将已经选过的数用一个数组来存

#include <iostream>using namespace std;const int N = 20;
int ways[N];
bool used[N];  //false代表没用 true代表用了
int n;//该函数代表下标u选哪个数
void dfs(int u)  //该u代表第几个数，也就是下标
{if(u > n)  //当u超过n时，代表前n个数已经选完了，可以输出了{for(int i = 1; i <= n; ++i){cout << ways[i] << " ";}puts("");return;}for(int i = 1; i <= n; ++i)  //从在第u位从1~n选一个数{if(used[i]) continue;  //若该数已经被使用了那就不选了used[i] = true;  //选该数ways[u] = i;  //把该数放到第u位dfs(u + 1);used[i] = false;  //不选该数}
}int main()
{cin >> n;dfs(1);return 0;
}

2.写法二：使用swap函数来变

该写法主要是通过先后顺序来替换了ways数组，也就是说采用交换位置的方式来一步步进行

#include <iostream>using namespace std;string str;
int n;void dfs(int u)
{if(u >= n){for(auto c: str){cout << c << " ";}puts("");return;}for(int i = u; i < n; ++i){swap(str[i], str[u]);dfs(u + 1);swap(str[i], str[u]);}
}int main()
{cin >> n;for(int i = 1; i <= n; ++i) str += i + '0';dfs(0);return 0;
}

三、组合型枚举

组合型枚举就是跟排列型枚举差不多，区别是，组合型枚举是从n个里面选m个（n >= m），也就是选到最后还会有的数没选，还有就是组合中123和132是同一个例子，所以意为组合而不是排列

写法一：用ways数组存

#include <iostream>using namespace std;const int N = 30;
int ways[N];
bool used[N];
int n, m;//另外关于组合，我这个是先选，之后如果递归没选的话，我这个数已经被用过了，也没事
void dfs(int u, int start)  //u代表在第u位上选啥，start代表从哪开始
{//u - 1 + n - start + 1 < mif (u + n - start < m) return;  // 剪枝if(u > m){for(int i = 1; i <= m; ++i){cout << ways[i] << " ";}cout << endl;return;}for(int i = start; i <= n; ++i){if(used[i]) continue;used[i] = true;ways[u] = i;dfs(u + 1, i + 1);used[i] = false;}
}int main()
{cin >> n >> m;dfs(1, 1);return 0;
}

写法二：用swap来做

#include <iostream>
#include <vector>using namespace std;vector<int> str;
int n, m;void dfs(int u, int start)
{if (u + n - start + 1 < m) return;  // 剪枝if(u >= m){for(int i = 0; i < m; ++i){cout << str[i] << " ";}puts("");return;}for(int i = start; i < n; ++i){swap(str[i], str[u]);dfs(u + 1, i + 1);swap(str[i], str[u]);}
}int main()
{cin >> n >> m;for(int i = 0; i < n; ++i) str.push_back(i+1);dfs(0,0);return 0;
}