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

Analysis

• 典型DFS, backtracking problem
• 和Permutations method 2方法类似

            [1]                        [2(1)]                          [2(2)]
    [1,2(1)]   [1,2(2)]          [2(1),1]   [2(1),2(2)]         [2(2),1]   [2(2),2(1)]
[1,2(1),2(2)] [1,2(2),2(1)]    [2(1),1,2(2)] [2(1),2(2),1]    [2(2),1,2] [2(2),2(1),1]

• 判断重复的条件：不是第一个数，且该数与前一个想同，且前一个visited标记为false

Code

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

    private void dfs(List<List<Integer>> result, List<Integer> list, int[] nums, boolean[] visited){
        if(list.size() == nums.length) {
            result.add(new ArrayList<Integer>(list));
            return;
        }

        for (int i=0; i<num.length; i++) {
            if (visited[i] || (i!=0 && num[i]==num[i-1] && !visited[i-1])) {continue;}
            visited[i] = true;
            current.add(num[i]);
            permute(result, current, num, visited);
            current.remove(current.size()-1);
            visited[i] = false;
        }
    }
}

Note

• boolean initialize default value in java: false

Reference

Leetcode
Same idea with explanation: yuanbin