2025年1317：【例5.2】组合的输出——全排列组合、组合选与不选

科技前沿 • 2025-02-17 23:05 • 阅读 52

大家好，我是讯享网，很高兴认识大家。

现要求你用递归的方法输出所有组合。

例如n＝5，r＝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

讯享网

【输入样例】
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. 全排列型组合，就要用上vis打标记，以及last参数来去重，递归结束条件就是u=m（一层），不是u=n,这个就不用cnt了，方案直接存a[u]里面了
2.组合型选与不选，不用vis，不用last参数，不用for循环，递归结束条件就是u=n，且当cnt=m满足输出条件，比起全排列多一层判断，所以说比全排列多一个cnt变量，记录方案的元素个数cnt，然后方案存的值，用u+1就行，因为他没for循环的 i
3. 对于1~n这种组合，一个保存答案数组即可，如果不是这种，自然多一个存储输入数据的数组

要知道u和last的含义，此题要把1到n这n个数的所有组合，每个组合r个数；
所以我们要去填充每个组合的r个空位置，所以从0开始搜索，也就是第一个空位，当搜到u==r时，也就是这r个空位以填满，这个组合已经组装好了，输出后回溯（return）；
需要注意组合要求当前数大于上一个，所以在当前i这个数往下深搜时，要判断下是否大于上一个数last；
注：去掉 i > last这个判断条件就是全排列了。

全排列型组合

#include <bits/stdc++.h> using namespace std; const int N = 25; int n, r; int path[N];//保存一个组合 int vis[N];//vis[i]表示i这个数在当前组合是否被用过 //u为这个组合的第几个位置 //last为这一组合上一个元素的值 void dfs(int u, int last) { 
    //当u=r,也就是这个组合已经组装好了，输出后回溯（return） if (u == r) { 
    for (int i = 0; i < r; ++i) { 
    printf("%3d", path[i]); } cout << endl; return; } //搜索1到n这n个数 for (int i = 1; i <= n; ++i) { 
    if (!vis[i] && i > last) { 
    vis[i] = 1; path[u] = i;//i可以放在路径的第u个位置 dfs(u + 1, i); vis[i] = 0; } } } int main() { 
    cin >> n >> r; dfs(0, 0); return 0; }

讯享网

组合型选与不选

讯享网#include <bits/stdc++.h> using namespace std; int n,r; int ans[25]; int cnt=0; void dfs(int u) { 
    if(u==n) { 
    if(cnt!=r) return; for(int i=0; i<r; i++) { 
    printf("%3d",ans[i]); } cout<<endl; return; } ans[cnt]=u+1; cnt++; dfs(u+1); //还原(回溯) cnt--; dfs(u+1); } int main() { 
    cin>>n>>r; dfs(0);//从第一次层搜索 return 0; }

写法二

从1开始搜索，这样可以用 path[u - 1]这个数（不会越界）当做搜索第u个数的的起始数，但要记着把vis[0]标记下；

#include <bits/stdc++.h> using namespace std; const int N = 25; int n, r; int path[N];//保存一个组合 int vis[N];//vis[i]表示i这个数在当前组合是否被用过 //u为这个组合的第几个位置 void dfs(int u) { 
    //当u=r+1,表示当前在搜第r+1个位置，但是该组合已经完成，也就是这个组合已经组装好了，输出后回溯（return） if (u == r + 1) { 
    for (int i = 1; i <= r; ++i) { 
    printf("%3d", path[i]); } cout << endl; return; } //搜索path[i-1]到n for (int i = path[u - 1]; i <= n; ++i) { 
    if (!vis[i]) { 
    vis[i] = 1; path[u] = i;//i可以放在路径的第u个位置 dfs(u + 1); vis[i] = 0; } } } int main() { 
    cin >> n >> r; vis[0] = 1; dfs(1); return 0; }

2025年1317：【例5.2】组合的输出——全排列组合、组合选与不选

分析

全排列型组合

组合型选与不选

写法二

相关推荐