To permute a set S, we can select the first character and
permute the rest of the characters of the string to get a new list of all possible permutations. Now
“push” the first character into each possible position.
For example, if our string is “abc”, we would do the following:
1. Let first = “a” and let remainder = “bc”.
2. Let list = permute(bc) = {“bc”, “cd”}.
3. Push “a” into each location of “bc” (--> “abc”, “bac”, “bca”)
and “cb” (--> “acb”, “cab”, “cba”) .
4. Return this new Arraylist.
