开发者社区云计算文章正文

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

2023-08-07 46

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 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, "");
}