LeetCode - Permutations | Darren's Blog

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]
Iterative Version
Loop through the array, in each iteration, a new number is added to different locations of results of previous iteration. Start from an empty List.
Code from http://www.programcreek.com/2013/02/leetcode-permutations-java/

public ArrayList<ArrayList<Integer>> permute(int[] num) {
 ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
 
 //start from an empty list
 result.add(new ArrayList<Integer>());
 
 for (int i = 0; i < num.length; i++) {
  //list of list in current iteration of the array num
  ArrayList<ArrayList<Integer>> current = new ArrayList<ArrayList<Integer>>();
 
  for (ArrayList<Integer> l : result) {
   // # of locations to insert is largest index + 1
   for (int j = 0; j < l.size()+1; j++) {
    ArrayList<Integer> temp = new ArrayList<Integer>(l);

                                temp .add(j, num[i]);

    current.add(temp);
   }
  }
 
  result = new ArrayList<ArrayList<Integer>>(current);
 }
 
 return result;
}

Recursive Version
We can also recursively solve this problem. Swap each element with each element after it.

public ArrayList<ArrayList<Integer>> permute(int[] num) {
 ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
 permute(num, 0, result);
 return result;
}
 
void permute(int[] num, int start, ArrayList<ArrayList<Integer>> result) {
 
 if (start >= num.length) {
  ArrayList<Integer> item = convertArrayToList(num);
  result.add(item);
 }
 
 for (int j = start; j <= num.length - 1; j++) {
  swap(num, start, j);
  permute(num, start + 1, result);
  swap(num, start, j);
 }
}
 
private ArrayList<Integer> convertArrayToList(int[] num) {
 ArrayList<Integer> item = new ArrayList<Integer>();
 for (int h = 0; h < num.length; h++) {
  item.add(num[h]);
 }
 return item;
}
 
private void swap(int[] a, int i, int j) {
 int temp = a[i];
 a[i] = a[j];
 a[j] = temp;
}

Use boolean visited array: code from http://blog.csdn.net/u010500263/article/details/18178243

public ArrayList<ArrayList<Integer>> permute(int[] num) {

        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

        ArrayList<Integer> element = new ArrayList<Integer>();

        boolean[] visited = new boolean[num.length];

        helper(num, result, element, visited);

        return result;

    }

    

    public void helper(int[] num, ArrayList<ArrayList<Integer>> result, ArrayList<Integer> element, boolean[] visited){

        if (element.size() == num.length){

            // duplicate element and add it to result (element would be changed from time to time. If directly use element

            // only result would be changed when element changed)

            result.add(new ArrayList<Integer>(element)); 

            return;

        }

        

        for(int i=0; i<num.length; i++){

            if(!visited[i]){

                visited[i] = true;

                element.add(num[i]);

                helper(num, result, element, visited);

                

                // After providing a complete permutation, pull out the last number, 

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

                visited[i] = false;

            }

        }

    }

Also refer to http://blog.csdn.net/u010500263/article/details/18178243
http://yucoding.blogspot.com/2013/04/leetcode-question-69-permutations.html
Read full article from LeetCode - Permutations | Darren's Blog