46. Permutations Leetcode Java

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:

Another classic recursion problem.

Recursion solution: 
1.base case: 

if(items.size()==num.length)){...}

2. Recursion steps:

try current candidate:used[i]=true;

                      items.add(num[i]);

recursion to next level: helper(res,items,num,used);

back track to current level: used[i]=false;

                             items.remove(items.size()-1);

Tips:

Skip used element, use a boolean array to track all the used element.

 public List<List<Integer>> permute(int[] num) {  
    List<List<Integer>> res=new ArrayList<List<Integer>>();  
    if(num==null || num.length==0) return res;  
    Arrays.sort(num);  
    boolean[] used=new boolean[num.length];  
    List<Integer> items= new ArrayList<Integer>();  
    helper(res,items,num,used);  
    return res;  
   }  
   public void helper(List<List<Integer>> res, List<Integer> items, int[] num, boolean[] used){  
     if(items.size()==num.length){  
       List<Integer> temp=new ArrayList<Integer>(items);  
       res.add(temp);  
       return;  
     }  
     for(int i=0;i<num.length;i++){  
       if(used[i]) continue;  
       used[i]=true;  
       items.add(num[i]);  
       helper(res,items,num,used);  
       used[i]=false;  
       items.remove(items.size()-1);  
       while(i+1<num.length && num[i+1]==num[i]) i++;  
     }  
   }  

Iteration solution: 
Assume we have an empty list, and a sorted array{1,2,3}, first we add 1 to the list,there is only one permutation to add 1 which is {1}, then we add 2 to the list, now we have two ways of insertion, one is before 1, the other is after 1, so now we have 2 permutations: {2,1},{1,2}. When we add 3 to the list, we have 3 ways of insertion, in position  0, 1,2 and we have two target list, so totally we can generate 6 permutations.{3,2,1},{2,3,1},{2,1,3},{3,1,2},{1,3,2},{1,2,3}. The iteration solution is based on the scenario.

 public List<List<Integer>> permute(int[] num) {  
    List<List<Integer>> res=new ArrayList<List<Integer>>();  
    if(num==null || num.length==0) return res;  
    Arrays.sort(num);  
    res.add(new ArrayList<Integer>());  
    for (int i=0;i<num.length;i++){  
      List<List<Integer>> newRes=new ArrayList<List<Integer>>();  
      int l=res.size();  
      for(int j=0; j<l;j++){  
       List<Integer> temp= res.get(j);  
        for(int k=0;k<=temp.size();k++){  
        List<Integer> item=new ArrayList<Integer>(temp);  
        item.add(k,num[i]);  
        newRes.add(item);  
        }  
      }  
      res=newRes;  
    }  
    return res;  
   }