The question isn’t worded very clearly in the book. The question is to find all subsets, including the empty set, and to find all combinations, not variations (i.e., ‘ac’ and ‘ca’ can be seen as the same).

We could modify the approach in permuteString, and as we build the permutations sort them and only add them if they don’t already exist. However, there is a cheaper and simpler way.

Again, if we have the word ‘cat’, we will start off with these subsets:

{} and {c}

Lets then go to ‘ca’

{}, {c}, {a}, {ca}

Well, that’s just {} and {c}, duplicated and with the ‘a’ added! Therefore we will duplicate all subsets and add ‘t’ to the duplicates for the final character:

{},{c},{a},{ca}, {t},{ct},{at},{cat}

We now have all subsets.