Permutations I && II

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

DFS，检查当前元素是否已经被加入。

public class Solution {
    //Time: O(n^n) 
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if (num == null || num.length == 0) {
            return res;
        }
        ArrayList<Integer> temp = new ArrayList<Integer>();
        permuteHelp(res, temp, num);
        return res;
    }
    
    private void permuteHelp(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> temp, int[] num) {
        if (temp.size() == num.length) {
            res.add(new ArrayList<Integer>(temp));
            return;
        }
        
        for (int i = 0; i < num.length; i++) {
            if (temp.contains(num[i])) {
                continue;
            }
            
            temp.add(num[i]);
            permuteHelp(res, temp, num);
            temp.remove(temp.size() - 1);
        }
    }
}

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

这题要考虑重复元素，需要一个boolean 数组来检查是否已经加入数组，同时对于相同的数字也要进行检测。

public class Solution {
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> tmp = new ArrayList<Integer>();
        Arrays.sort(num);
        boolean[] visit = new boolean[num.length];
        permutate(res, tmp, num, visit);
        return res;
    }
    
    private void permutate(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> tmp, 
                           int[] num, boolean[] visit) {
        if (tmp.size() == num.length) {
            res.add(new ArrayList<Integer>(tmp));
            return;
        }
        
        for (int i = 0; i < num.length; i++) {
            if (visit[i] || (i != 0 && num[i] == num[i - 1] && !visit[i - 1])) {
                continue;
            }
            visit[i] = true;
            tmp.add(num[i]);
            permutate(res, tmp, num, visit);
            tmp.remove(tmp.size() - 1);
            visit[i] = false;
        }
    } 
}