Permutation

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].

Hint: Select a number from beginning to the end, then permute the remaining numbers recursively. Tips: use a boolean array used[ ] to track which numbers have been selected in the current permutation sequence.

01 public ArrayList<ArrayList<Integer>> permute(int[] num) {
02     boolean []used=new boolean[num.length];
03     ArrayList<Integer>temp=new ArrayList<Integer>();
04     ArrayList<ArrayList<Integer>>result=new ArrayList<ArrayList<Integer>>();
05     doPermute(num,result,temp,used,0);
06     return result;
07   
08 }
09 public void doPermute(int []num, ArrayList<ArrayList<Integer>>result,ArrayList<Integer>temp,boolean[]used, int level)
10 {
11     if(level==num.length)
12     {
13         ArrayList<Integer> out=new ArrayList<Integer>();
14         for(int i=0;i<temp.size();i++)
15         {
16             out.add(temp.get(i));
17         }
18         result.add(out);
19         return;
20     }
21   
22     for(int i=0;i<num.length;i++)
23     {
24         if(!used[i])
25         {
26             temp.add(num[i]);
27             used[i]=true;
28             doPermute(num,result,temp,used,level+1);
29             used[i]=false;
30             int size=temp.size();
31             if(size>0)
32             {
33                 temp.remove(size-1);
34             }
35         }
36     }
37 
38 }