全组合—动态规划_动态规划的所有组合

#include<iostream>
#include<string>
#include<vector>
using namespace std;
 
vector<string> result;
int hashtable[26]={0};
bool flag=false;
 
int main()
{
	string a;
	cin>>a;
	int len=a.length();
	int i;
	for(i=0;i<len;i++)
	{
		int count=result.size();
		int k;
		int index=a[i]-'a';
		for(k=0;k<count;k++)
		{	
			if(hashtable[index]==0)
			{
				string temp=result[k]+a[i];
				result.push_back(temp);
			}
			else
			{
				string temp=result[k];
				int j;
				int count=0;
				for(j=0;j<temp.length();j++)
				{
					if(temp[j]==a[i])
						count++;
				}
				if(count==hashtable[index])
				{
					flag=true;
					string temp=result[k]+a[i];
					result.push_back(temp);
				}
			}
		}
		hashtable[index]++;
		if(!flag)
		{
			string b(1,a[i]);
			result.push_back(b);
			flag=false;
		}
	}
	vector<string>::iterator p= result.begin();
	for(p;p!=result.end();p++)
		cout<<*p<<endl;
	return 0;
 
}

全组合的意思： 比如输入三个字母 A , B, C。 则把它们可能的组合全部打印出来： A, B, C, AB, AC, BC, ABC。 

策略：

      使用动态规划。逐个字母地访问。用一个vector<string> 保存到目前为止可能的组合。比如对于A，B, C 输入序列。动态规划的结果是

1. A

2. A,   AB,  B

3. A,   AB,  B,  AC,  ABC,  BC, C

通过模拟，我们应该能发现，若输入序列为ABCC（即输入序列中含有相同的字母，则这种方法会答应出重复的组合）。采取的方法是：建立一个hash表，记录输入序列中每个单词出现的次数。比如对于第二个C，此时C出现的次数已经为1.则只需添加动态规划中含有C一次的那些组合。

1. A
2. A,   AB,  B
3. A,   AB,  B,  AC,  ABC,  BC, C

4. A,   AB,  B,  AC,  ABC,  BC, C, ACC, ABCC, BCC, CC

参考代码：