Generating all possible permutations of the string This generates all possible permutations of the string.  I am also unable to understand the time complexity of this problem. Can someone please explain the complexity to me?

import java.util.ArrayList;


public class permutations {

    public ArrayList&lt;String&gt; performPermutations(String s){
        ArrayList&lt;String&gt; arrayList = new ArrayList&lt;String&gt;();
        if (s == null) {
            return null;
        }

        else if (s.length() == 0) {
            arrayList.add("");
            return arrayList;
        }

        else {
            for (int i = 0; i &lt; s.length(); i++) {
                ArrayList&lt;String&gt; remaining = performPermutations(s.substring(0, i) + s.substring(i + 1));
                for (int j = 0; j &lt; remaining.size(); j++) {
                    arrayList.add(s.charAt(i) + remaining.get(j));
                }
            }
            return arrayList;
        }
    }


    public static void main(String[] args) {
        permutations p = new permutations();
        ArrayList&lt;String&gt; arr = p.performPermutations("abcde");
            for(int i = 0; i&lt;arr.size();i++) {
                System.out.println(arr.get(i));
            }
        }
    }
}
There are quite a few ways this code can be improved:


All class names should start with a capital, and be in CamelCase. Specifically, the class permutations should be Permutations. The way it doesn't look like a variable, as in here:

permutations p = new permutations();



performPermutations method


Why does it declare a return type of ArrayList&lt;String&gt;? Is there anything special about the implementation of the list? It should just be List&lt;String&gt;.
You have an unnecessary if-else structure, since each if statement returns a value. You can remove all of the elses.
In the first if statement, you return null. This is a bad idea in many cases. An empty list would be more favorable, just in case any calling code wants to operate on it immediately afterwards. (Notice that your main method would fail with a NullPointerException if the passed in list was empty).
You can combine the first and second if statements into one. This would be your "base" case:

if (s == null || s.isEmpty() { return arrayList; }


Never compare a list length to 0, use isEmpty() instead. Also, s is a poor name for a method parameter. Try to be creative and descriptive. Finally, there's no need to add an empty string if the list is empty.
There's a lot of existing posts on string permutations you may find interesting. Seeing a recursive call embedded in two for loops is probably unnecessarily complex.


How this method could look (but can still be improved):

public List&lt;String&gt; performPermutations(final String s){

    final List&lt;String&gt; result = new ArrayList&lt;String&gt;();

    if (s == null) {
        return result;
    }

    for (int i = 0; i &lt; s.length(); i++) {
        final List&lt;String&gt; remaining = performPermutations(s.substring(0, i) + s.substring(i + 1));
        for (int j = 0; j &lt; remaining.size(); j++) {
            result.add(s.charAt(i) + remaining.get(j));
        }
    }

    return result;
}