全排列II

47. 全排列 II

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

在搜索前对候选数组排序，一旦发现某个分支搜索下去可能搜索到重复的元素就停止搜索。

我们可以画出下面的递归图（来自liweiwei）：

以[1, 1, 2] 为例，我们需要保证只出现一次 [1, 1, 2]，在上图中有两种情况，搜索的是同一个数字

• 在图中②处，搜索的数和上一次一样，但上一次的1还在使用中。
• 在图中①处，搜索的数和上一次一样，但上一次的1刚刚被撤销，由于它已经被撤销，有可能后面的搜索还会使用到它，因此会产生重复，需要剪掉它。

在全排列的 DFS 代码中需要添加如下代码来进行剪枝

if(i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]){
    continue;
}

class Solution {
    List<List<Integer>> ans;
    boolean[] visited;

    public List<List<Integer>> permuteUnique(int[] nums) {
        int len = nums.length;
        ans = new ArrayList<List<Integer>>();
        visited = new boolean[len];
		
        //排序是剪枝的基础
        Arrays.sort(nums);
        dfs(nums, 0, new ArrayDeque<Integer>(len));
        return ans;
    }

    public void dfs(int[] nums, int index, Deque<Integer> path){
        int len = nums.length;
        if(index == len){
            ans.add(new ArrayList<Integer>(path));
            return;
        }

        for(int i = 0; i < len; i++){
            if(visited[i]){
                continue;
            }
            
			// 剪枝条件：i > 0 是为了保证 nums[i - 1] 有意义
            // 写 !used[i - 1] 是因为 nums[i - 1] 在深度优先遍历的过程中刚刚被撤销选择
            if(i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]){
                continue;
            }

            visited[i] = true;
            path.addLast(nums[i]);

            dfs(nums, index + 1, path);

            path.removeLast();
            visited[i] = false;
        }
    }
}