Permutations II(Medium)

LeetCode Source

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

解题思路1：回溯+DFS

与I不同的是这里允许了重复的元素 ,所以如果当前访问元素与之前元素相同而之前的元素没有访问过 说明相似的情况已经出现过 要避免再出现

复杂度

时间O(n!) 空间栈 O(n!)

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    if (nums == null || nums.length == 0) return result;

    List<Integer> list = new ArrayList<Integer>();
    boolean[] visited = new boolean[nums.length];

    Arrays.sort(nums);
    dfs(nums, list, result,visited);

    return result;
}

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

    for (int i = 0; i < nums.length; i++) {
        if(!visited[i]) {
    //only insert duplicate element when the previous duplicate element has been inserted
            if (i > 0 && nums[i] == nums[i-1] && visited[i-1] == false){
                continue;
            }

            current.add(nums[i]);
            visited[i] = true;
            dfs(nums, current, result,visited);
            current.remove(current.size() - 1);
            visited[i] = false;
        }
    }//for
}

解题思路2: 迭代,使用Next Permutaion的思想

Permutation I 的迭代法也适用与这个问题。