元素的组合（dfs）

无重复元素的组合

输入一串小些字母（无重复字母），从中取出k(k<10)个字母，输出组合情况。
样例：
输入：
abcd
3
输出：
abc
abd
acd
bcd

一道搜索的题，想办法建图或是画搜索树。

这里推荐建图的方法，因为是组合情况，不用考虑顺序，也就是说，元素一样，顺序不一样算同一种组合。

那么为了避免重复组合，就应该规定一个组合顺序，比如ASCII值从小到大。

那么这道题的图就是一个有向图的遍历了。

从每一个结点开始遍历，累计遍历到结点数等于k时，输出。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<cstring>
 6 using namespace std;
 7 #define rep(i, a, n) for(int i = a; i <= n; ++i) 
 8 #define per(i, n, a) for(int i = n; i >= a; --i)
 9 typedef long long ll;
10 int len, k, tot = 0;
11 char a[15], ans[15];
12 int vis[500];
13 void print(int tot)
14 {
15     rep(i, 1, k) printf("%c", ans[i]); printf("
");
16 }
17 void solve(char id, int step)
18 {
19      if(step == k + 1) print(++tot); 
20     for(int i = id; i <= 'z'; ++i)    //从这个结点的ASCII值开始，尝试走到所有比他大的结点 
21     {
22         if(vis[i])        //结点存在 
23         {    
24             ans[step] = i; vis[i] = 0; 
25             solve(i, step + 1);        
26             vis[i] = 1;
27         }
28     }
29 }
30 
31 int main()
32 {
33 //    freopen("p4.in", "r", stdin);
34 //    freopen("p4.out", "w", stdout);
35     scanf("%s%d", a, &k);
36     len = strlen(a);
37     sort(a, a + len);
38     rep(i, 0, len - 1) vis[a[i]] = 1;
39     solve('a', 1);    
40     return 0;
41 }

有重复元素的组合

输入一串小些字母（有重复字母），从中取出k 个字母，输出组合情况。
样例：
输入：
aabbcc
4
输出：
1:aabb
2:aabc
3:aacc
4:abbc
5:abcc
6:bbcc

这下元素有重复了，若还是按上述方式建图

会发现，从结点a有三条出边b（左下）,b（右下）,c。而从左下角的b走到c，和从右下角的b走到c得到的组合相同。所以对于每一个结点的出边指向的结点，其种类应该是两两不相同的，也就是说，图应该改为这样

然后遍历所有点就行了。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<cstring>
 6 using namespace std;
 7 #define rep(i, a, n) for(int i = a; i <= n; ++i) 
 8 #define per(i, n, a) for(int i = n; i >= a; --i)
 9 typedef long long ll;
10 int len, k, tot = 0;
11 char a[15], ans[15];
12 int vis[500];
13 void print(int tot)
14 {
15     printf("%d:", tot);
16     rep(i, 1, k) printf("%c", ans[i]); printf("
");
17 }
18 void solve(char id, int step)
19 {
20      if(step == k + 1) print(++tot); 
21     for(int i = id; i <= 'z'; ++i)
22     {
23         if(vis[i])
24         {    
25             ans[step] = i; vis[i]--;     //该点走过了 
26             solve(i, step + 1);        
27             vis[i]++;
28         }
29     }
30 }
31 
32 int main()
33 {
34 //    freopen("p5.in", "r", stdin);
35 //    freopen("p5.out", "w", stdout);
36     scanf("%s%d", a, &k);
37     len = strlen(a);
38     sort(a, a + len);
39     rep(i, 0, len - 1) vis[a[i]]++;
40     solve('a', 1);    
41     return 0;
42 }