A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

Anagram Generation

To top off our conversation, let’s tackle our most complex recursive problem yet. We’re going to use everything we’ve got in our recursion toolbox to make this work.

We’re going to write a function that returns an array of all anagrams of a given string. An anagram is a reordering of all the characters within a string. For example, the anagrams of "abc" are:

["abc",
"acb",
"bac",
"bca",
"cab",
"cba"]

Now, let’s say we were to collect all the anagrams of the string "abcd". Let’s apply our top-down mindset to this problem.

Presumably, we could say that the subproblem of "abcd" is "abc". The question then, is: if we had a working anagrams function that returned all the anagrams of "abc", how can we use them to produce all ...