目錄
遞歸實現(xiàn)排列型枚舉
遞歸實現(xiàn)排列類型枚舉 II
?遞歸實現(xiàn)組合型枚舉
遞歸實現(xiàn)組合型枚舉 II
遞歸實現(xiàn)指數(shù)型枚舉
遞歸實現(xiàn)指數(shù)型枚舉 II
遞歸不是循環(huán)，遞歸利用了系統(tǒng)棧，只要是函數(shù)都會被系統(tǒng)管理。當(dāng)執(zhí)行到函數(shù)地址入口時就會為函數(shù)在系統(tǒng)棧上分配一塊內(nèi)存。當(dāng)函數(shù)在自己內(nèi)部再次調(diào)用自己，那么系統(tǒng)又會給此時調(diào)用的函數(shù)再次分配內(nèi)存，結(jié)果說就是層層調(diào)用。遞歸就是這么回事。
遞歸實現(xiàn)排列型枚舉
把?1～n?這?n?個整數(shù)排成一行后隨機(jī)打亂順序，輸出所有可能的次序。
輸入格式
一個整數(shù)?n。
輸出格式
按照從小到大的順序輸出所有方案，每行?1?個。
首先，同一行相鄰兩個數(shù)用一個空格隔開。
其次，對于兩個不同的行，對應(yīng)下標(biāo)的數(shù)一一比較，字典序較小的排在前面。
數(shù)據(jù)范圍
1≤n≤9
輸入樣例：
3
輸出樣例：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1#include<iostream>
using namespace std;
const int N=10;
bool st[N];
int g[N];
int n;
void dfs(int u)
{
if(u==n)
{
for(int i=0;i<n;i++) cout<<g[i]<<" ";
cout<<endl;
}
for(int i=1;i<=n;i++)
{
if(!st[i])
{
g[u]=i;
st[i]=true;
dfs(u+1);
st[i]=false;
}
}
}
int main()
{
cin>>n;
dfs(0);
return 0;
}遞歸實現(xiàn)排列類型枚舉 II
給定一個長度為?n?的可包含重復(fù)數(shù)字的序列，請你求出其所有不重復(fù)的全排列。
輸入格式
第一行包含整數(shù)?n。
第二行包含?n?個整數(shù)。
輸出格式
輸出所有的不同排列，每種排列占一行。
在確定每種排列的輸出順序時，第一個數(shù)較小的先輸出，第一個數(shù)相同時，第二個數(shù)較小的先輸出，以此類推。
數(shù)據(jù)范圍
1≤n≤9
數(shù)組中包含的元素的取值范圍?[1,9]
輸入樣例：
3
1 1 2
輸出樣例：
1 1 2
1 2 1
2 1 1?
#include<iostream>
#include<algorithm>
using namespace std;
const int N=10;
bool st[N];
int a[N];
int g[N];
int n;
void dfs(int u)
{
if(u==n)
{
for(int i=0;i<n;i++) cout<<g[i]<<" ";
cout<<endl;
return ;
}
for(int i=1;i<=n;i++)
{
//剪枝1
if(!st[i])
{
st[i]=true;
g[u]=a[i];
dfs(u+1);
st[i]=false;
//這一步就是剪枝2 很nice
while(a[i]==a[i+1]) i++;
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n);
dfs(0);
return 0;
}?遞歸實現(xiàn)組合型枚舉
從?1～n 這?n?個整數(shù)中隨機(jī)選出?m?個，輸出所有可能的選擇方案。
輸入格式
兩個整數(shù)?n,m?在同一行用空格隔開。
輸出格式
按照從小到大的順序輸出所有方案，每行?1?個。
首先，同一行內(nèi)的數(shù)升序排列，相鄰兩個數(shù)用一個空格隔開。
其次，對于兩個不同的行，對應(yīng)下標(biāo)的數(shù)一一比較，字典序較小的排在前面（例如?1 3 5 7?排在?1 3 6 8?前面）。
數(shù)據(jù)范圍
n>0
0≤m≤n
n+(n?m)≤25
輸入樣例：
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
思考題：如果要求使用非遞歸方法，該怎么做呢？
#include<iostream>
#include<algorithm>
using namespace std;
const int N=25;
int g[N];
bool st[N];
int n,m;
void dfs(int u,int start)
{
if(u==m)
{
for(int i=0;i<m;i++) cout<<g[i]<<" ";
cout<<endl;
return ;
}
for(int i=start;i<=n;i++)
{
if(!st[i])
{
st[i]=true;
g[u]=i;
dfs(u+1,i+1);
st[i]=false;
}
}
}
int main()
{
cin>>n>>m;
dfs(0,1);
return 0;
}遞歸實現(xiàn)組合型枚舉 II
給定一個長度為?n?的可包含重復(fù)數(shù)字的序列，從中隨機(jī)選取?m?個數(shù)字，輸出所有可能的選擇方案。
輸入格式
第一行包含兩個整數(shù)?n,m。
第二行包含?n?個正整數(shù)。
輸出格式
按照從小到大的順序輸出所有方案，每行?1?個。
首先，同一行內(nèi)的數(shù)升序排列，相鄰兩個數(shù)用一個空格隔開。
其次，對于兩個不同的行，對應(yīng)下標(biāo)的數(shù)一一比較，字典序較小的排在前面（例如1 3 5 7排在1 3 6 8前面）。
數(shù)據(jù)范圍
n>0
0≤m≤n
n+(n?m)≤25
序列內(nèi)所有元素均不大于?n。
輸入樣例：
5 3
1 2 2 3 3
輸出樣例：
1 2 2
1 2 3
1 3 3
2 2 3
2 3 3#include<iostream>
#include<algorithm>
using namespace std;
const int N=25;
int a[N];
int g[N];
bool st[N];
int n,m;
void dfs(int u,int start)
{
if(u==m)
{
for(int i=0;i<m;i++) cout<<g[i]<<" ";
cout<<endl;
}
for(int i=start;i<=n;i++)
{
//只留下相同的數(shù)的第一個取組合 不能是 while(a[i-1]==a[i])i++;這樣的話不能構(gòu)成122
//只有輪到第2個2開始排的時候需要跳過 前一個2已經(jīng)恢復(fù)現(xiàn)場顧加上！st[i-1]可以使其跳過
if(i != 0 && !st[i-1] && a[i-1] == a[i]) continue;
g[u]=a[i];
st[i] = true;
dfs(u+1, i+1);
st[i] = false;
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n);
dfs(0,1);
return 0;
}遞歸實現(xiàn)指數(shù)型枚舉
從?1～n?這?n?個整數(shù)中隨機(jī)選取任意多個，輸出所有可能的選擇方案。
輸入格式
輸入一個整數(shù)?n。
輸出格式
每行輸出一種方案。
同一行內(nèi)的數(shù)必須升序排列，相鄰兩個數(shù)用恰好?1?個空格隔開。
對于沒有選任何數(shù)的方案，輸出空行。
本題有自定義校驗器（SPJ），各行（不同方案）之間的順序任意。
數(shù)據(jù)范圍
1≤n≤15
輸入樣例：
3
輸出樣例：
3
2
2 3
1
1 3
1 2
1 2 3#include<iostream>
using namespace std;
const int N=16;
int g[N];
bool st[N];
int n;
void dfs(int u,int start)
{
if(u<=n)
{
for(int i=0;i<u;i++) cout<<g[i]<<" ";
cout<<endl;
}
for(int i=start;i<=n;i++)
{
if(!st[i])
{
st[i]=true;
g[u]=i;
dfs(u+1,i+1);
st[i]=false;
}
}
}
int main()
{
cin>>n;
dfs(0,1);
return 0;
}#include<iostream>
#include<algorithm>
using namespace std;
const int N=20;
int g[N];
int n;
void dfs(int u,int start)
{
if(u<=n)
{
for(int i=0;i<u;i++) cout<<g[i]<<" ";
cout<<endl;
}
for(int i=start;i<=n;i++)
{
g[u]=i;
dfs(u+1,i+1);
}
}
int main()
{
cin>>n;
dfs(0,1);
}?
遞歸實現(xiàn)指數(shù)型枚舉 II
給定一個長度為?n?的可包含重復(fù)數(shù)字的序列，從中隨機(jī)選取任意多個數(shù)字，輸出所有可能的選擇方案。
輸入格式
第一行包含一個整數(shù)?n，表示序列長度。
第二行包含?n?個正整數(shù)。
輸出格式
每行輸出一種方案。
同一行內(nèi)的數(shù)必須升序排列，相鄰兩個數(shù)用恰好1個空格隔開。
對于沒有選任何數(shù)的方案，輸出空行。
本題有自定義校驗器（SPJ），各行（不同方案）之間的順序任意。
數(shù)據(jù)范圍
1≤n≤15
序列內(nèi)所有元素均不大于?n。
輸入樣例：
3
1 2 2
輸出樣例：文章來源：http://www.zghlxwxcb.cn/news/detail-616291.html
1
2
1 2
2 2
1 2 2#include<iostream>
#include<algorithm>
using namespace std;
const int N=16;
int g[N];
int a[N];
bool st[N];
int n;
void dfs(int u,int start)
{
if(u<=n)
{
for(int i=0;i<u;i++) cout<<g[i]<<" ";
cout<<endl;
}
for(int i=start;i<=n;i++)
{
if(!st[i])
{
st[i]=true;
g[u]=a[i];
dfs(u+1,i+1);
st[i]=false;
while(a[i]==a[i+1]) i++;
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n);
dfs(0,1);
return 0;
}#include<iostream>
#include<algorithm>
using namespace std;
const int N=16;
int g[N];
int a[N];
bool st[N];
int n;
void dfs(int u,int start)
{
if(u<=n)
{
for(int i=0;i<u;i++) cout<<g[i]<<" ";
cout<<endl;
}
for(int i=start;i<=n;i++)
{
if(i!=1&&!st[i-1]&&a[i]==a[i-1]) continue;
st[i]=true;
g[u]=a[i];
dfs(u+1,i+1);
st[i]=false;
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n);
dfs(0,1);
return 0;
}?文章來源地址http://www.zghlxwxcb.cn/news/detail-616291.html
到了這里，關(guān)于遞歸實現(xiàn) 組合問題+排列問題（DFS)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
