permute.java

public class Solution {
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if (num.length == 0) return null;
        ArrayList<Integer> intList = new ArrayList<Integer>();
        ArrayList<Integer> prefix = new ArrayList<Integer>();
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        for (int index = 0; index < num.length; index++)
        {
            intList.add(num[index]);
        }
        return permute2(prefix, intList, result);
    }
    
    public ArrayList<ArrayList<Integer>> permute2(ArrayList<Integer> prefix, ArrayList<Integer> list, ArrayList<ArrayList<Integer>> result) {
        //System.out.println(list + ": " + list.size());
        //System.out.println(prefix);
        if (list.size() == 0) {
            //System.out.println("Added");
            ArrayList<Integer> temp = new ArrayList<Integer>(prefix);
            result.add(temp);
            return result;
        }
        
        for(int i=0; i < list.size(); i++) {
            prefix.add(list.get(i));
            list.remove(i);
            permute2(prefix, list, result);
            list.add(prefix.get(i));
            prefix.remove(i);
        }
        
        //System.out.println(result);
        return result;
    }
}