Generating all permutations of a given string

public static void permutation(String str) {     permutation("", str); }private static void permutation(String prefix, String str) {    int n = str.length();    if (n == 0) System.out.println(prefix);    else {        for (int i = 0; i < n; i++)            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));    }}

(via Introduction to Programming in Java)

Use recursion.

• Try each of the letters in turn as the first letter and then find all the permutations of the remaining letters using a recursive call.
• The base case is when the input is an empty string the only permutation is the empty string.

Here is my solution that is based on the idea of the book "Cracking the Coding Interview" (P54):

/** * List permutations of a string. *  * @param s the input string * @return  the list of permutations */public static ArrayList<String> permutation(String s) {    // The result    ArrayList<String> res = new ArrayList<String>();    // If input string's length is 1, return {s}    if (s.length() == 1) {        res.add(s);    } else if (s.length() > 1) {        int lastIndex = s.length() - 1;        // Find out the last character        String last = s.substring(lastIndex);        // Rest of the string        String rest = s.substring(0, lastIndex);        // Perform permutation on the rest string and        // merge with the last character        res = merge(permutation(rest), last);    }    return res;}/** * @param list a result of permutation, e.g. {"ab", "ba"} * @param c    the last character * @return     a merged new list, e.g. {"cab", "acb" ... } */public static ArrayList<String> merge(ArrayList<String> list, String c) {    ArrayList<String> res = new ArrayList<>();    // Loop through all the string in the list    for (String s : list) {        // For each string, insert the last character to all possible positions        // and add them to the new list        for (int i = 0; i <= s.length(); ++i) {            String ps = new StringBuffer(s).insert(i, c).toString();            res.add(ps);        }    }    return res;}

Running output of string "abcd":

• Step 1: Merge [a] and b:[ba, ab]

• Step 2: Merge [ba, ab] and c:[cba, bca, bac, cab, acb, abc]

• Step 3: Merge [cba, bca, bac, cab, acb, abc] and d:[dcba, cdba, cbda, cbad, dbca, bdca, bcda, bcad, dbac, bdac, badc, bacd, dcab, cdab, cadb, cabd, dacb, adcb, acdb, acbd, dabc, adbc, abdc, abcd]