ZJYYC 活字印刷 DFS

ZJYYC 活字印刷 DFS 题目描述:

活字印刷术是中国古代四大发明之一，今天我们要试着用计算机实现一个“活字印刷术”。现在输入一个字符串s,代表一套活字字模，其中每个字模上都刻有一个字母 s[i]。输出你可以印出的非空字母序列的数目。

输入描述:

输入数据由多组测试数据组成。每组测试数据第一行输入一个字符串s ( 1 <= s.length <= 10 ），s中所有字母均为大写字母

输出描述:

输出可以印出的非空字母序列数目

测试样例:

样例输入 1

AAB

样例输出 1

8

提示:

对于样例： 可能的序列为 "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA"。

是真的笨比，这个题目我也没有想明白，我最开始想着把每种情况都存下来，然后去重的，t过了也m过了，后来发现我是笨蛋。。。。。

可以先把所有的字母都统计出来，然后每一位都尝试放一个字母，由于遍历的是26个字母，就不会有重复的情况（比如“AAA”，只有“A”， “AA”， “AAA”）

然后每次尝试前ans++，因为放下一个字母就会形成一个不同的字母序列

#include
using namespace std;

int arr[30]; 
string s;
int ans;
void dfs(){
	for(int i = 0; i < 26; i++){
		if(arr[i]){
			ans++;
			arr[i]--;
			dfs();
			arr[i]++;
		}
	}
}

int main(){
	
	while(cin >> s){
		memset(arr, 0, sizeof(arr));
		int len = s.length();
		ans = 0;
		for(int i = 0; i < len; i++){
			arr[s[i] - 'A']++;
		}
		dfs();
		cout << ans << endl;
	}
	return 0;
}