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: 排列组合 -> 循环＋递归
这道题跟N-Queens，Sudoku Solver，Combination Sum，Combinations等一样，也是一个NP问题。方法还是原来那个套路，还是用一个循环递归处理子问题。区别是这里并不是一直往后推进的，前面的数有可能放到后面，所以我们需要维护一个used数组来表示该元素是否已经在当前结果中，因为每次我们取一个元素放入结果，然后递归剩下的元素，所以不会出现重复。时间复杂度还是NP问题的指数量级。

Reference: http://blog.csdn.net/linhuanmars/article/details/21569031

public class Solution {
    public ArrayList> permute(int[] num) {
        ArrayList> list = new ArrayList>();
        if(num == null || num.length == 0) 
            return list;
            
        boolean[] used = new boolean[num.length];
        ArrayList cur = new ArrayList();
        select(num, cur, list, used);
        return list;
    }
    
    public void select(int[] num, ArrayList cur, ArrayList> list, boolean[] used) {
        if(cur.size() == num.length) {
            list.add(new ArrayList(cur));
        }
        
        for(int i = 0; i < num.length; i++) {
            if(!used[i]) {
                used[i] = true;
                cur.add(num[i]);
                select(num, cur, list, used);
                
                //after completing a permutation, remove the elements
                cur.remove(cur.size() - 1);  
                used[i] = false;
            }
        }
    }
}