枚举的三种类型--指数型&排列型&组合型
枚举的三种类型
指数型枚举
指数型枚举
#include <bits/stdc++.h> using namespace std; int n; int arr[20]; void dfs(int cur,int m) { if(cur == n + 1) { for(int i = 1;i < m;i++) cout<<arr[i]<<" "; puts(" "); //puts()函数的作用与语句“printf("%s\n",s);的作用相同。注意:puts在输出字 符串后会自动输出一个回车符。 return; } dfs(cur + 1,m);//不选,仍为m个数 arr[m] = cur;//选出第cur个数 dfs(cur + 1,m + 1);//选第cur个数 } int main() { cin>>n; dfs(1,1); return 0; } /* 4 4 3 3 4 2 2 4 2 3 2 3 4 1 1 4 1 3 1 3 4 1 2 1 2 4 1 2 3 1 2 3 4 */
排列型枚举
排列型枚举
#include <bits/stdc++.h> using namespace std; int n; int arr[30]; bool vis[30]; void dfs(int cur) { if(cur == n + 1) { for(int i = 1; i <= n; ++i) cout << arr[i] << " "; puts(""); return; } for(int i = 1; i <= n; ++i) { if(vis[i]) continue; arr[cur] = i; vis[i] = true; dfs(cur + 1); vis[i] = false; } } int main() { cin >> n; dfs(1); return 0; } */ /* 3 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 */
组合型枚举
组合型枚举
#include <bits/stdc++.h> using namespace std; int n, m; int arr[30]; bool vis[30]; void dfs(int cur) { if(cur == m + 1) { for(int i = 1; i <= m; ++i) cout << arr[i] << " "; puts(""); return ; } for(int i = 1; i <= n; ++i) { if(vis[i] || i < arr[cur - 1]) continue; arr[cur] = i; //Ñ¡µÚi¸öÊý vis[i] = true; dfs(cur + 1); vis[i] = false; //»Ö¸´ } } int main() { cin >> n >> m; dfs(1); return 0; }*/ /* 3 2 1 2 1 3 2 3 */