Permutations II

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

参考：http://www.cnblogs.com/remlostime/archive/2012/11/13/2768816.html

思路是一样的，不过要控制一下不能出现重复的排列。先将原数组排序，然后在控制排列的序列在原来的序列一样就不会出现重复的排序了。

先对数组进行排序，这样在DFS的时候，可以先判断前面的一个数是否和自己相等，相等的时候则前面的数必须使用了，自己才能使用，这样就不会产生重复的排列了。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


public class Solution {
    private boolean visited[];
    
    public List<List<Integer>> permuteUnique(int[] num) {
        visited = new boolean[num.length];
        Arrays.sort(num);
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        DFS(num, 0, result, new ArrayList<Integer>());
        
        return result;
    }
    
    private void DFS(int num[], int dep, List<List<Integer>> result, List<Integer> cur){
        if(dep == num.length){
            result.add(new ArrayList<Integer>(cur));
            return;
        }

        for(int i = 0; i < num.length; i++){
            if(i >0 && num[i] == num[i - 1] && visited[i - 1] == false)
                continue;
            if(visited[i] == false)
            {
                cur.add(num[i]);
                visited[i] = true;
                DFS(num,  dep + 1, result, cur);
                cur.remove(cur.size() - 1);
                visited[i] = false;
            }//if
        }//for
        
    }
}