UVa 598

題目

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

給有一群字串，輸出這群字串的所有組合

想法

這題跟問數字 $1$~$n$ 的所有組合是相同的問題，只是從數字變成字串而已，但是概念相同
因為求的是組合，所以過去出現過的組合就不能再以不同排列出現
也就是說要是我們已經枚舉過包含元素 $A$ 的所有組合，那下次元素 $A$ 就必定不能再使用
所以可以用一個變數 $start$ 紀錄上次最後用到哪個元素，下次枚舉就從 $start+1$ 開始即可

這題麻煩的是輸入有些複雜，可以使用 stringstream 處理輸入是 a 或是 a b 的情況

Code

//By Koios1143
#include<iostream>
#include<sstream>
using namespace std;
int m, a, b, R, res[20];
string op, s, arr[20];
bool used[20];

void DFS(int depth, int start, int end){
	if(depth == end){
		for(int i=0 ; i<end ; i++){
			if(i) cout<<", ";
			cout<<arr[res[i]];
		}
		cout<<"\n";
		return;
	}
	for(int i=start ; i<R ; i++){
		res[depth]=i;
		DFS(depth+1, i+1, end);
	}
}

int main(){
	// 輸入
	cin>>m;
	while(getchar() != '\n');
	while(getchar() != '\n');
	for(int t=0 ; t<m ; t++){
		if(t) cout<<"\n";
		R = 0;
		getline(cin, op);
		while(getline(cin, s) && s[0]!='\0'){
			arr[R] = s;
			R++;
		}
		
		// 判斷所求是哪種
		if(op[0] == '*'){
			a=1, b=R+1;
		}
		else{
			stringstream ss;
			ss<<op;
			ss>>a;
			ss>>b;
			// 判斷有沒有 b
			if(ss.fail()){
				b=a+1;
			}
			else{
				b++;
			}
		}
		
		for(int i=a ; i<b ; i++){
			if(i>a) cout<<"\n";
			cout<<"Size "<<i<<"\n";
			DFS(0, 0, i);
		}
		cout<<"\n";
	}

	return 0;
}