UVa 10776

題目

http://domen111.github.io/UVa-Easy-Viewer/?10776

本題有多筆測資，每筆測資包含一個字串 $s$ 以及一個數字 $r$，求以 $s$ 為集合，所有長度為 $r$ 的字串組合，每個輸出字串由小到大排列

想法

因為要求的是組合，我們可以去枚舉答案的第 $i$ 格要是什麼，並且過去枚舉過的字就不能再使用

為了避免重複枚舉到重複的字串，一開始要先把字串由小到大排序好

Code

//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
string s, res[35];
int n;

void DFS(int depth, int start){
	// 枚舉完 n 個字了
	if(depth == n){
		for(int i=0 ; i<n ; i++){
			cout<<res[i];
		}
		cout<<"\n";
		return;
	}
	
	// 第 i 個字不能重複
	// 用 used 紀錄用過的字
	bool used[26];
	for(int i=0 ; i<26 ; i++){
		used[i] = false;
	}
	// 前面娶過的字不會再被用到
	// 從 start 開始枚舉
	for(int i=start ; i<s.size() ; i++){
		if(!used[s[i]-'a']){
			used[s[i]-'a']=true;
			res[depth] = s[i];
			DFS(depth+1, i+1);
		}
	}
}

int main(){
	while(cin>>s>>n){
		sort(s.begin(), s.end());
		DFS(0, 0);
	}
	return 0;
}

時間複雜度分析

每筆測資輸入時間複雜度為 $O(|s|)$，令 $n = |s|$

每筆測資排序時間複雜度為 $O(nlogn)$

DFS 每一層最多有 $|s|$ 種選擇，總共有 $|s|$ 層

每筆測資 DFS 時間複雜度為 $O(n^n)$

每筆測資總時間複雜度為 $O(nlogn + n^{n+1})$