47.Permutations II

https://leetcode.com/problems/permutations-ii/

1.Description(Medium)

Given a list of numbers with duplicate number in it. Find all unique permutations.

Example

For numbers[1,2,2]the unique permutations are:

[
  [1,2,2],
  [2,1,2],
  [2,2,1]
]

2.Code

http://www.cnblogs.com/grandyang/p/4359825.html

http://www.jiuzhang.com/solutions/permutations-ii/

对于这道题。也是要求permutation,大体上的解题思路和Permutations是相同的，但是不同点在哪里呢？ 不同点为：

1. 这个给定的数组中可能会含有相同的数字.

2. 最后答案不接受重复相同的答案组.

3. 要先将数组排序，确保重复的元素是在一起的。

4. 除了不能加入之前出现过的元素之外，还不能加入本轮搜索中出现过的元素。

对于这两点要求，Permutations的解法是无法解决的，所以我们就要考虑怎样满足以上两个要求. 我们可以对整个input数组进行排序，在求解答案的时候，只要一个元素的permutation求出来了，在这个元素后面和这个元素相同的元素，我们完全都可以pass掉，其实这个方法在sum和combination里面已经是屡试不爽了.

解题思路: 除了加上对于重复答案的处理外，剩下思路同Permutation一模一样。

时间复杂度: O(n!)

由于输入数组有可能出现重复数字，如果按照之前的算法运算，会有重复排列产生，我们要避免重复的产生，在递归函数中要判断前面一个数和当前的数是否相等，如果相等，前面的数必须已经使用了，即对应的visited中的值为1，当前的数字才能使用，否则需要跳过，这样就不会产生重复排列了

public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result=new ArrayList<>();
        if(nums==null){
            return result;
        }
        if(nums.length==0){
            result.add(new ArrayList<Integer>());
            return result;
        }
        List<Integer> path=new ArrayList<Integer>();
        boolean[] visited=new boolean[nums.length];
        Arrays.sort(nums);
        dfs(nums,path,result,visited);
        return result;
    }

    public void dfs(int[] nums,List<Integer> path,List<List<Integer>> result,boolean[] visited){
        if(path.size()==nums.length){
            result.add(new ArrayList<Integer>(path));
            return;
        }
        for(int i=0;i<nums.length;i++){
            /*
         上面的判断主要是为了去除重复元素影响。
         比如，给出一个排好序的数组，[1,2,2]，那么第一个2和第二2如果在结果中互换位置，
         我们也认为是同一种方案，所以我们强制要求相同的数字，原来排在前面的，在结果
         当中也应该排在前面，这样就保证了唯一性。所以当前面的2还没有使用的时候，就
         不应该让后面的2使用。
            */
            if(visited[i] || (i>0 && nums[i]==nums[i-1] && visited[i-1]==false)){
                continue;
            }
            visited[i]=true;
            path.add(nums[i]);
            dfs(nums,path,result,visited);
            path.remove(path.size()-1);
            visited[i]=false;           
        }
    }