UVa 441

題目

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

給一個正整數 $k$ 以及 $k$ 個由小到大排序好的數字，輸出所有序列長度為 $6$ 的組合，所有組合皆由小到大輸出

$6 < k < 13$

想法

因為題目要求組合而非排列，所以說像是 $(1, 2, 3)$ 和 $(2, 1, 3)$ 會被視為相同的

所以我們可以這麼想，這些會被視為相同的組合在由小到大排序過後都是一樣的

所以我們可以直接找那個由小到大嚴格遞增的那個，在上例中就是 $(1, 2, 3)$

既然 $k$ 不大，我們就可以考慮使用 DFS 去枚舉出所有的狀況

並且為了保持每個組合的遞增性，記錄上次最後存取的元素位置，下次就只能從那個位置之後繼續枚舉

例如說給定的序列是 ${1, 2, 3, 4}$

現在枚舉到 ${1, 3}$ 的時候，下次就不需要再看 $3$ 以前的數字了，只需要看 $3$ 以後的數字

如此一來，我們就可以在維持序列遞增性的前提下去枚舉出所有情況了!

Code

//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
int n, m, tmp[6], arr[15], res[10];

void dfs(int depth, int start){
	// 已經找好六個數字了 
	if(depth == 6){
		// 把結果複製到 tmp 
		for(int i=0 ; i<6 ; i++){
			tmp[i] = res[i];
		}
		for(int i=0 ; i<6 ; i++){
			if(i) cout<<" ";
			cout<<tmp[i];
		}
		cout<<"\n";
		return;
	}
	// 從 start 開始枚舉
	for(int i=start ; i<n ; i++){
		res[depth] = arr[i];
		dfs(depth+1, i+1);
	}
}
int main(){
	bool out=false;
	while(cin>>n && n){
		if(out) cout<<"\n";
		else out=true;
		
		for(int i=0 ; i<n ; i++){
			cin>>arr[i];
		}
		dfs(0, 0);
	}
	
	return 0;
}

時間複雜度分析

每筆測資輸入時間複雜度為 $O(n)$

DFS 每一層最多會有 $n$ 個選擇，總共有 $6$ 層

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

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