有关回溯的相关 排列组合遍历
目录
最近刚刚学习了递归，回溯算法来进行深度搜索。对一些题目有一些感触，顺便写下变体的解法。
此类深搜主要分为无相同元素和有相同元素，下面又分好几种情况。
无相同元素
全排列
void dfs(int i){
if(n==i){
for(int j=0;j<n;j++)
printf("%5d",a[j]);
printf("\n");
}
else
for(int j=1;j<=n;j++)
if(b[j]==0){
b[j]=1;
a[i]=j;
dfs(i+1);
b[j]=0;
}
}例题1：
问题 A: 全排列问题
时间限制: 1 Sec 内存限制: 128 MB
提交: 123 解决: 71
[提交][状态][讨论版][命题人: 外部导入]题目描述
输出自然数1到n所有不重复的排列，即n的全排列，要求所产生的任一数字序列中不允许出现重复的数字。
输入
输入 n(1≤n≤9)
输出
由1～n组成的所有不重复的数字序列，每行一个序列。每个数字占5列。
样例输入
4样例输出
1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 1 4 3 3 1 2 4 3 1 4 2 3 2 1 4 3 2 4 1 3 4 1 2 3 4 2 1 4 1 2 3 4 1 3 2 4 2 1 3 4 2 3 1 4 3 1 2 4 3 2 1
排列A（n,m）
void dfs(int i,int l){
if(l==n){
for(int j=0;j<n;j++)
cout<<b[j];
cout<<"\n";
}else
for(int j=0;j<m;j++)
if(a[j]==0){
a[j]=1;
b[i]=j+1;
dfs(i+1,l+1);
a[j]=0;
}
}
例题2：
问题 B: 输出N个不同字母的全排列
时间限制: 1 Sec 内存限制: 128 MB
提交: 223 解决: 83
[提交][状态][讨论版][命题人: 外部导入]题目描述
输入正整数n（n＜10），输出ABCD...n个不同字母的全排列，输出时按升序每行显示一个结果
输入
正整数N（N＜10）
输出
N个字母的全排列，升序排列，每行一个
样例输入
【测试样例1】 1 【测试样例2】 2 【测试样例3】 3 【测试样例4】 4样例输出
【测试样例1】 A 【测试样例2】 AB BA 【测试样例3】 ABC ACB BAC BCA CAB CBA 【测试样例4】 ABCD ABDC ACBD ACDB ADBC ADCB BACD BADC BCAD BCDA BDAC BDCA CABD CADB CBAD CBDA CDAC CDCA DABC DACB DBAC DBCA DCAB DCBA
组合C（n,m）
void dfs(int i,int l,int k){
if(l==n){
for(int j=0;j<n;j++)
cout<<b[j];
cout<<"\n";
}else
for(int j=k;j<m;j++){
if(a[j]==0){
a[j]=1;
b[i]=j+1;
dfs(i+1,l+1,k);
a[j]=0;
}
k++;
}
}例题3：
问题 D: 组合的输出
时间限制: 1 Sec 内存限制: 128 MB
提交: 111 解决: 64
[提交][状态][讨论版][命题人: 外部导入]题目描述
排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且r<＝n)，我们可以简单地将n个元素理解为自然数1，2，…，n，从中任取r个数。
现要求你用递归的方法输出所有组合。
例如n＝5，r＝3，所有组合为：
l 2 3 l 2 4 1 2 5 l 3 4 l 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5
输入
一行两个自然数n、r(1<n<21，1<＝r<＝n)。
输出
所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。
样例输入
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<map>
using namespace std;
int n,m;
int a[15]={0};
char b[15];
char c[15];
map<char,int> counts;
void dfs(int i){
if(i==n){
for(int j=0;j<n;j++)
cout<<b[j];
cout<<"\n";
}else{
for(map<char,int>::iterator it=counts.begin();it!=counts.end();it++)
if(it->second!=0){
b[i]=it->first;
it->second--;
dfs(i+1);
it->second++;
}
}
}
int main(){
char c;
cout<<"有相同元素全排列"<<endl;
cin>>n;
cout<<"输入元素"<<endl;
for(int i=0;i<n;i++){
cin>>c;
if(counts.count(c)==0)
counts[c]=1;
else
counts[c]++;
}
dfs(0);
}例题4：
问题 E: 有重复元素的排列问题
时间限制: 1 Sec 内存限制: 128 MB
提交: 147 解决: 62
[提交][状态][讨论版][命题人: 外部导入]题目描述
设R={ r1, r2 , …, rn}是要进行排列的n个元素。其中元素r1, r2 , …, rn可能相同。试设计一个算法，列出R的所有不同排列。
给定n 以及待排列的n 个元素。计算出这n 个元素的所有不同排列。
输入
输入数据的第1 行是元素个数n，1≤n≤500。接下来的1 行是待排列的n个元素。
输出
计算出的n个元素的所有不同排列并输出。文件最后1行中的数是排列总数。
样例输入
4 aacc样例输出
aacc acac acca caac caca ccaa 6
例题5：
问题 C: 排列棋子
时间限制: 1 Sec 内存限制: 128 MB
提交: 135 解决: 96
[提交][状态][讨论版][命题人: 外部导入]题目描述
将M个白棋子与N个黑棋子排成一行，可以排成多种不同的图案。例如：2个白棋子和2个黑棋子，一共可以排成如下图所示的6种图案（根据组合数计算公式：
）
请你编写一段程序，输出M个白棋子与N个黑棋子能够组成的所有图案。
为了避免程序输出结果过多导致严重超时，特别限制：1≤M,N≤6
输入
两个正整数M,N表示白棋子与黑棋子的数量，并且满足1≤M,N≤6
输出
M个白棋子与N个黑棋子可以排列的所有图案。
要求：每行输出一种图案，白棋子用0表示，黑棋子用1表示，按升序输出样例输入
<span style="color:#333333">【测试样例1】 2 1 【测试样例2】 2 2 【测试样例3】 2 3</span>样例输出
<span style="color:#333333">【测试样例1】 001 010 100 【测试样例2】 0011 0101 0110 1001 1010 1100 【测试样例3】 00111 01011 01101 01110 10011 10101 10110 11001 11010 11100</span>提示
shj
以上例题均来自WLACM
上一篇： 图的DFS && BFS遍历
下一篇： 回溯8.括号生成