[Java] Generate string permutations recursively

Ahhhh, string permutations. The timeless classic. Also painfully slow with its O(N!) time and space complexity. Let's put a twist on it and do it recursively just because we can.

Also, just because we can, we use StringBuilders instead of Strings. Is this a good idea? Is the cost of creating lots of StringBuilders offsetting the cost of creating a new String object everytime? That's what method timing is for, we'll leave this as "exercise" for the reader.

Anyway, enough introduction, let's go to the meat: we call a recursive method which will have as input the size of the result string to create, the string we built so far, the string of unused characters so far and the output collection.

Then, for each unused character, we add it to the current string and recurse on the remaining ones leaving that out. The base case is when we no longer have characters to use; if the string we built is the correct length, we add it to the result set and return, otherwise simply return.

Note: StringBuilder.deleteCharAt alters the source directly instead of returning a new object, therefore calling this method as StringBuilder(x.deleteCharAt) and StringBuilder(x).deleteCharAt makes quite the difference!

You can check the implementation on my Gist along with some test cases in PermutateJTests.