c++ - Generate subsequences

Question

I have a string like "0189", for which I need to generate all subsequences, but the ordering of the individual characters must be kept, i.e, here 9 should not come before 0, 1 or 8. Ex: 0, 018, 01, 09, 0189, 18, 19, 019, etc.

Another example is "10292" for which subsequences would be: 1, 10, 02, 02, 09, 29, 92, etc. As you might have noticed '02' two times, since '2' comes twice in the given string. But again things like: 21, 01, 91 are invalid as order is to be maintained.

Any algorithm or psuedo code, which could be implemented in C/C++ would be appreciated!

Answer 1

Try a recursive approach:

• the set of subsequences can be split into the ones containing the first character and the ones not containing it
• the ones containing the first character are build by appending that character to the subsequences which don't contain it (+ the subsequence which contains only the first character itself)