cniks117's blog

By cniks117, 11 years ago, In English

how can we print all possible subsequences of string using dynamic programming. for ex . for sequence 1,2,3 the possible subsequences are {1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}

Tags dp
  • Vote: I like it
  • -5
  • Vote: I do not like it

| Write comment?
»
11 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Here's the code how this could be done using recursion with caching. But, you can't do it faster than the number of all possible combinations:

#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<vector<string> > cache;
string s;
int n;

void subseq(int to)
{
	string tmp = "";
	for (int i = to - 1; i >= 0; i--)
	{
		if (cache[i].size() == 0)
			subseq(i);

		for (int j = 0; j < cache[i].size(); j++)
		{
			tmp = cache[i][j] + s[to - 1];
			cache[to].push_back(tmp);

			cout << tmp << endl;
		}
	}
}

int main()
{
	cin >> s;
	n = s.length();

	for (int i = 0; i <= n; i++)
		cache.push_back(vector<string>());
	cache[0].push_back("");

	subseq(n);

	return 0;
}