题目描述
从n个字符(n从a开始,依次递增)中选取r个字符,对r个字符进行不重复排列。字典序小的在前面。
输入描述
一行,n和r
输出描述
r个字符的所有组合,每种组合占一行,字符和字符之间用空格隔开。
样例输入
样例输出
样例说明
数字3代表c,就是从a,b,c三个中任选两个进行不重复组合。
题目分析
(1)一道搜索与回溯的题目,不同的是要输出不重复的组合
(2)可以直接对字符进行操作
(3)因为题目比较特殊,可以直接对数字排序, 然后由数字转换成字符
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
| #include<iostream> using namespace std; int n,r; int pd[100],ans[100]; void print() { int i; for(i=1; i<=r; i++) printf("%c ",ans[i]+'a'-1); cout<<endl; } void dfs(int k) { int i; if(k==r){ print(); return; } for(i=ans[k]; i<=n; i++) { if(pd[i]==0) { pd[i]=1; ans[k+1]=i; dfs(k+1); pd[i]=0; } } } int main() { cin>>n>>r; ans[0]=1; dfs(0); return 0; }
|