I'm working on a program (using C++) that has a list of words in a vector: {"one", "two", "three", "four"} for example, and I'd need to get all possible partitions respecting the order and where subsets contain one or at most two words.
For example:
{"one", "two", "three", "four"} {"one two", "three", "four"} {"one two", "three four"} {"one", "two three", "four"} .. etc
Note that both the order of the set is maintained and no repetition is allowed. Note also that {"one two three", "four"} wouldn't be valid as each subset can have 2 elements at most.
As I'm working in C++, I was thinking if it's possible to make an algorithm that could tell me how to generate all possible sets. Avoiding recursion would be preferable, as I presume I could run into some stack overflow issues on some platforms.
For example, something that generated a sequence like
(1,1,1,1), (2,1,1), (2,2), (1,2,1), etc. (basically, stating the size of each subset) would be what I'm looking for.
Any help is greatly appreciated.