Woodstock Blog

a tech blog for general algorithmic interview questions

[CC150v4] 8.4 Generate Permutation Recursively


Write a method to compute all permutations of a string.

Do it recursively.


  1. Get first char.

  2. Permute the reminder of the string.

  3. Insert that char into all possible positions.

The code is more concise that doing it iteratively, and no visited array needed!


public static ArrayList<String> getPerms(String s) {
    ArrayList<String> ans = new ArrayList<String>();
    if (s.length() == 1) {
        return ans;
    char single = s.charAt(0);
    ArrayList<String> partialPerms = getPerms(s.substring(1));
    for (String part : partialPerms) {
        for (int i = 0; i <= part.length(); i++) {
            ans.add(part.substring(0, i) + single + part.substring(i));
    return ans;