Cacher is the code snippet organizer for pro developers

/**
 * Given a collection of numbers that might contain duplicates, return all possible unique permutations.
 * For example,
 * [1,1,2] have the following unique permutations:
 * [1,1,2], [1,2,1], and [2,1,1].
 */
 public class Solution {
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
    	if (num == null)
			return null;
		Arrays.sort(num);
		boolean[] used = new boolean[num.length];
		return perm(num, 0, used);
	}

	public ArrayList<ArrayList<Integer>> perm(int[] num, int l, boolean[] used) {
		ArrayList<ArrayList<Integer>> rl = new ArrayList<ArrayList<Integer>>();
		if (l == num.length)
			rl.add(new ArrayList<Integer>());
		else {
			for (int i = 0; i < num.length; i++) {
				// for i is used and i - 1 is not used.
				if (used[i] || i != 0 && num[i] == num[i - 1] && !used[i - 1])
					continue;
				used[i] = true;
				for (ArrayList<Integer> x : perm(num, l + 1, used)) {
					x.add(0, num[i]);
					rl.add(x);
				}
				used[i] = false;
			}
		}
		return rl;
	}
	
	public ArrayList<ArrayList<Integer>> permuteUniqueRecursion(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if(num == null || num.length == 0)
            return result;
        ArrayList<Integer> list = new ArrayList<Integer>();
        int[] visited = new int[num.length];
        
        Arrays.sort(num);
        helper(result, list, visited, num);
        return result;
    }
    
    public void helper(ArrayList<ArrayList<Integer>> result, ArrayList<Integer> list, int[] visited, int[] num) {
        if(list.size() == num.length) {
            result.add(new ArrayList<Integer>(list));
            return;
        }
		
        for(int i = 0; i < num.length; i++) {
            if (visited[i] == 1 || (i != 0 && num[i] == num[i - 1] && visited[i - 1] == 0)){
		// 上面的判断其实并不影响最终结果，目的是为了让dfs能更快
		/*
			上面这一连串判断条件，重点在于要能理解!visited.contains(i-1)
			要理解这个，首先要明白i作为数组内的序号，i是唯一的
			给出一个排好序的数组，[1,2,2]
			第一层递归			第二层递归			第三层递归
			[1]					[1,2]				[1,2,2]
		        序号:[0]				 [0,1]			[0,1,2]
			这种都是OK的，但当第二层递归i扫到的是第二个"2"，情况就不一样了
			[1]					[1,2]				[1,2,2]			
                         序号:[0]				[0,2]				[0,2,1]
			所以这边判断的时候!visited.contains(0)就变成了true，不会再继续递归下去，跳出循环
			步主要就是为了去除连续重复存在的，很神奇反正 = =||
	*/
				continue;
			}
            visited[i] = 1;
            list.add(num[i]);
            helper(result, list, visited, num);
            list.remove(list.size() - 1);
            visited[i] = 0;
        }
    }
	
}

/**
 * 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].
 */
 public class Solution {
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> a = new ArrayList<Integer>();
        a.add(num[0]);
        res.add(a);
        for(int i = 1; i < num.length; i++){
            res = insert(res, num[i]);
        }
        return res;
    }
    
    public ArrayList<ArrayList<Integer>> insert(ArrayList<ArrayList<Integer>> res, int num){
        ArrayList<ArrayList<Integer>> r = new ArrayList<ArrayList<Integer>>();
        for(int i = 0; i < res.size(); i++){
            for(int j = 0; j < res.get(i).size() + 1; j++){
                ArrayList<Integer> temp = new ArrayList<Integer>(res.get(i));
                temp.add(j, num);
                r.add(temp);
            }
        }
        return r;
    }
    
    public List<List<Integer>> permuteRecursive(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(nums == null || nums.length == 0) return res;
        helper(nums, new ArrayList<Integer>(), res);
        return res;
    }
    public void helper(int[] nums, List<Integer> path, List<List<Integer>> res) {
        if(path.size() == nums.length) {
            res.add(new ArrayList<Integer>(path));
            return;
        }
        for(int i = 0; i < nums.length; i++) {
            if(path.contains(nums[i])) continue;
            path.add(nums[i]);
            helper(nums, path, res);
            path.remove(path.size() - 1);
        }
    }
 }