#include <stdio.h>
#include <vector>
#include <string>
#include <set>
#include <iostream>
#include <stdlib.h>

using namespace std;

#define MAX_WORD_SZ 20 // max length of a word

set<string> dict; // words I can use

void initialize_dict(){
	dict.insert("how");
	dict.insert("are");
	dict.insert("you");
	dict.insert("h");
	dict.insert("o");
	dict.insert("w");
}

// "inseartSpaces" in stream starting at position start
vector<vector<string>> insertSpaces(string stream, int start){
	int l = stream.length();
	vector<vector<string>> result;
	result.clear(); // make sure result is empty

	// find word at beginning of stream
	string word = "";
	for(int i=start; i<l && i<MAX_WORD_SZ ; ++i){
		word += stream[i];

		if( dict.find(word) != dict.end() ){
			vector<vector<string>> aux = insertSpaces(stream, i+1);
			if( i+1 == l ){
				vector<string> wl;
				wl.push_back(word);
				result.push_back(wl);
				//return result; // result is a list of one list with a word in it
			}
			else if( aux.size() != 0 ){
				int sz = aux.size();
				vector<string> wl;
				for(int j=0; j<sz; ++j ){
					wl.clear();
					wl.push_back(word);
					wl.insert(wl.end(), aux[j].begin(), aux[j].end());
					result.push_back(wl);
				}
			}

		}
	}

	return result; // will be empty list
}

void solve_recursive(string stream){
	printf("Recursive solution:\n");
	vector<vector<string>> result;
	result = insertSpaces(stream, 0);

	for(auto it=result.begin(); it!=result.end(); ++it){
		for(auto it2=it->begin(); it2!=it->end(); ++it2)
			cout << *it2 << " ";
		cout << "\n";
	}

	cout<< "\n";
}

int main(){
	initialize_dict();

	solve_recursive("howareyou");
	solve_recursive("how");
	solve_recursive("ho");
	//solve_iterative(inputString);

	return 0;
}