字符全排列(2)
【题目描述】
从n个字符(n从a开始，依次递增)中选取r个字符，对r个字符进行不重复排列。字典序小的在前面。
【输入描述】
一行，n和r
【输出描述】
r个字符的所有组合，每种组合占一行，字符和字符之间用空格隔开。
【样例输入】
3 2
【样例输出】
a b a c b c
【样例说明】
数字3代表c，就是从a,b,c三个中任选两个进行不重复组合。
【题目分析】
(1)一道搜索与回溯的题目,不同的是要输出不重复的组合
(2)可以直接对字符进行操作
(3)因为题目比较特殊，可以直接对数字排序， 然后由数字转换成字符
【参考代码1】
#include<bits/stdc++.h>
using namespace std;
int n,r; //定义一共几个数，需要选几个数
int pd[100],ans[100];//pd数组是判断是否用过这个数，ans是结果数组
void print() { //输出函数
int i;
for(i=1; i<=r; i++) //根据规模范围输出
printf("%c ",ans[i]+'a'-1);//由原来的数字改成字符
cout<<endl;
}
void dfs(int k) { //深搜函数，当前是第k格
int i;
if(k==r){ //填满了的时候
print();//输出当前解
return;
}
for(i=ans[k]; i<=n; i++) { //1-n循环填数,先从上一步的数据开始，
if(pd[i]==0) { //如果当前数没有用过
pd[i]=1;//标记一下,1表示当前这个数字使用过
ans[k+1]=i;//把这个数填入结果数组
dfs(k+1);//填下一个
pd[i]=0;//回溯
}
}
}
int main() {
cin>>n>>r;//读入规模和要选几个数
ans[0]=1;// 因为要用到上一步的值，所以开始的时候要给初值，不然就会取到0
dfs(0);//注意，这里是从第0格开始的！
return 0;
}
(adsbygoogle = window.adsbygoogle || []).push({});