Permutations

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

Solution:

public class Solution {
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        if(num.length == 0) return null;
        ArrayList<ArrayList<Integer>> prev = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> firstElm = new ArrayList<Integer>();
        firstElm.add(num[0]);
        prev.add(firstElm);
        if(num.length == 1) return prev;
        
        for(int i = 1; i < num.length; i++){
            prev = insertElmFirst(prev, num[i]);
        }
        return prev;
    }
    
    public ArrayList<ArrayList<Integer>> insertElmFirst(ArrayList<ArrayList<Integer>> allArrayList, int value){
        ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
        for(ArrayList<Integer> arrayList : allArrayList){
            insertElmSecond(results, arrayList, value);
        } 
        return results;
    }
    public void insertElmSecond(ArrayList<ArrayList<Integer>> results, ArrayList<Integer> arrayList, int value){
        for(int pos = 0; pos < arrayList.size() + 1; pos++){
            ArrayList<Integer> newArrayList = new ArrayList<Integer>();
            for(int left = 0; left < pos; left++){
                newArrayList.add(arrayList.get(left));
            }
            newArrayList.add(value);
            for(int right = pos+1; right < arrayList.size() + 1; right++){
                newArrayList.add(arrayList.get(right-1));
            }
            results.add(newArrayList);
        }
    }
}