UVa10776 - Determine The Combination(有重复元素的组合问题)

#include <cstdio>#include <cstring>#include <string>#include <algorithm>#include <cctype>usingnamespacestd;
constintN=26;
strings;
intr;
intcnt[N];
intnumber[N], n;
charch[N];
boolinput();
voidsolve();
voiddfs(intcur, intdep, strings);
intmain()
{
#ifndef ONLINE_JUDGEfreopen("d:\\OJ\\uva_in.txt", "r", stdin);
#endifwhile (input()) {
solve();
    }
return0;
}
boolinput()
{
charbuf[N+10];
if (scanf("%s%d", buf, &r) !=2) returnfalse;
s=buf;
sort(s.begin(), s.end());
memset(cnt, 0x00, sizeof(cnt));
for (size_ti=0; i<s.length(); i++) {
cnt[s[i] -'a']++; 
    }
n=0;
for (inti=0; i<N; i++) {
if (cnt[i] !=0) {
number[n] =cnt[i];
ch[n++] =i+'a';
        }
    }
returntrue;
}
voiddfs(intcur, intdep, strings)
{
if (dep==r) {
printf("%s\n", s.c_str());;
return;
    }
for (inti=cur; i<n; i++) {
if (number[i] >0) {
number[i]--;
stringtmp=s;
tmp.append(1, ch[i]);
dfs(i, dep+1, tmp);
number[i]++;
        }
    }
}
voidsolve()
{
dfs(0, 0, "");
}