Permutations of any given numbers I have solved one programming problem where we have to find all the permutations of given numbers.

For example, \$[1,2,3]\$ have the following permutations:

$$[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]$$

I have written the code for it and my code successfully cleared all the tests. But, I am not really sure about its complexity.

public List&lt;List&lt;Integer&gt;&gt; permute(int[] num) {
    List&lt;List&lt;Integer&gt;&gt; res=new ArrayList&lt;List&lt;Integer&gt;&gt;();
    res.add(new ArrayList&lt;Integer&gt;()); // Add an empty list
    for(int number = 0; number &lt; num.length; number++)
    {
        List&lt;List&lt;Integer&gt;&gt; curr = new ArrayList&lt;List&lt;Integer&gt;&gt;();
        for(List&lt;Integer&gt; nestedL : res)
        {
            for(int j = 0; j &lt; nestedL.size() + 1 ;j++)
            {
                nestedL.add(j,num[number]);
                List&lt;Integer&gt; temp = new ArrayList(nestedL);
                curr.add(temp);
                nestedL.remove(j);
            }
        }
        res = new ArrayList&lt;List&lt;Integer&gt;&gt;(curr);
    }

   return res;
}


First, look at the algorithm, which suggests that it is a \$O(n^3)\$. But, I am not sure if it it correct. Would somebody like to throw more light on the complexity of this algorithm?
public List&lt;List&lt;Integer&gt;&gt; permute(int[] num) {


I'd call num, numbers.  In fact, I try to always name collections with a plural.  Also, I write names out rather than abbreviate them.  It will make things much easier if you ever have to read the code in the future.  

List&lt;List&lt;Integer&gt;&gt; res=new ArrayList&lt;List&lt;Integer&gt;&gt;();


It would be helpful here to explain why res is a list of lists.  Why not just a single list?  Maybe this would be obvious to me if you came up with a more descriptive name.  I'm guessing that res is short for result.  I would have probably named it permutations.  

res.add(new ArrayList&lt;Integer&gt;()); // Add an empty list


When commenting, try to say why you are doing things rather than what you are doing.  E.g.  // Add an empty list so that the middle for loop runs.  

This seems odd though.  You pass in an int[].  Why not make a list of integer arrays then?  If that makes something not work, comment on it so that you don't regress it later.  

    for(List&lt;Integer&gt; nestedL : res)
    {


Note that res can contain all the permutations (of which there are \$n!\$).  This is what gives you your \$O(n!)\$ time.  Note that it's actually \$O(n^3n!)\$ time, but the \$n!\$ eats the \$n^3\$.  

        for(int j = 0; j &lt; nestedL.size() + 1 ;j++)


This would be better if you pulled the nestedL.size() + 1 out of the comparison.  

        for(int j = 0, n = nestedL.size() + 1; j &lt; n ; j++)


It seems like you should be able to do a bit better here.  There's a lot of list creation and copying, which seems unnecessary.  

            nestedL.add(j,num[number]);
            List&lt;Integer&gt; temp = new ArrayList(nestedL);
            curr.add(temp);
            nestedL.remove(j);


Ok, you add an element to a list; then you copy the list; save the copy; finally, you remove the added element from the original list.  Why not reorder things like so

            List&lt;Integer&gt; temp = new ArrayList(nestedL);
            temp.add(j, num[number]);
            curr.add(temp);


That saves a remove operation.  

This also highlights a problem with the name number.  It's not a number from the num array.  It's an index to the array.  I'd name it either i or index.  

public List&lt;List&lt;Integer&gt;&gt; permute(int[] numbers) {
    // we use a list of lists rather than a list of arrays 
    // because lists support adding in the middle
    // and track current length
    List&lt;List&lt;Integer&gt;&gt; permutations = new ArrayList&lt;List&lt;Integer&gt;&gt;();
    // Add an empty list so that the middle for loop runs
    permutations.add(new ArrayList&lt;Integer&gt;());

    for ( int i = 0; i &lt; numbers.length; i++ ) {
        // create a temporary container to hold the new permutations 
        // while we iterate over the old ones
        List&lt;List&lt;Integer&gt;&gt; current = new ArrayList&lt;List&lt;Integer&gt;&gt;();
        for ( List&lt;Integer&gt; permutation : permutations ) {
            for ( int j = 0, n = permutation.size() + 1; j &lt; n; j++ ) {
                List&lt;Integer&gt; temp = new ArrayList&lt;Integer&gt;(permutation);
                temp.add(j, numbers[i]);
                current.add(temp);
            }
        }
        permutations = new ArrayList&lt;List&lt;Integer&gt;&gt;(current);
    }

    return permutations;
}