UVa 10776 Determine The Combination

想法：

直接舉例子來講，假設字串aaabbc(編號012345)，取3個(n==3)，我們先假設ans這個容器來存放所選的字元。

首先進入第一層遞迴後，表示要選一個字元放到ans[0]，能選的字元為0~5，for loop 0~5，先放0('a')到ans。然後進入第二層遞迴，能選的字元變成1~5，for loop 1~5，放入1('a')到ans。再進入第三層遞迴，能選的字為2~5，for loop 2~5，放入2('a')到ans。進入第四層遞迴後發現ans.size()==n，因此輸出答案。

接下來退出第四層回到第三層，跳出ans的字(ans.pop_back())，找下一個字元，因為避免重複，所以用while loop找到下一個不一樣的字，放入3('b')到ans，以此類推...

把第三層for loop跑完後，回到第二層，一樣跳出第二層的字，找下一個字不一樣的字元，然後繼續進入第三層。....剩下以此類推。

	#include <iostream>
	//#include <cstdio>
	#include <vector>
	#include <algorithm>
	using namespace std;
	string str;
	int n;
	void choose_ch (vector<char> &ans,int start)
	{
	if (ans.size() == n) {
	for (char &c : ans)
	cout << c;
	cout << endl;
	return;
	}
	for (int i = start; i < str.size(); ){
	char c = str[i];
	ans.push_back(c);
	choose_ch (ans, i+1);
	ans.pop_back();
	while (str[i] == c) i++;
	}
	}
	int main()
	{
	ios::sync_with_stdio(false);
	// freopen ("input.txt","rt",stdin);
	while (cin >> str >> n){
	sort(str.begin(), str.end());
	vector<char> ans;
	choose_ch(ans, 0);
	}
	return 0;
	}

view raw [UVa] 10776 Determine The Combination.cpp hosted with ❤ by GitHub