全排列II

---

title: 全排列II
categories: 数据结构与算法

---

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

示例:

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

主要思路:整体思路和全排列是大致相同的，本题的难点在于如何剪枝，如何去重

如图所示，当我们把nums数组排好序后，我们思考一个问题，什么时候会产生重复的组合，红色框内标注的情况是和1是一样的，所以当num[i-1]==nums[i]时，可能会发生重复，当我们是要判断层重复，而不是枝重复，如果仅仅只有这个条件那么最左边一条路径在选取第二个i时，也无法选择
所以我们还需要另一个判重条件
我们在深入分析可以发现，其实我们要剪枝的部分是满足上述条件且刚刚撤销选择的部分，当我们撤销选择时，在重新选取下一个数时，如果num[i-1]==num[i]说明下面的情况都相同
剩下的代码和全排列相同

public class PermuteUnique {
	
	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		int [] nums = {1};
		List<List<Integer>> permuteUnique = permuteUnique(nums);
		for(List list:permuteUnique)
			System.out.println(list.toString());
	}
	public static List<List<Integer>> permuteUnique(int[] nums) {
		if(nums.length == 0)
			return null;
		Arrays.sort(nums);
		boolean []used = new boolean[nums.length];
		//推荐使用Deque来创建stack类
		Deque<Integer> path = new ArrayDeque();
		List<List<Integer>> res = new ArrayList<>();
		dfs(0, nums,used,path,res);
		return res;
    }
	public static void dfs(int depth,int[] nums,boolean[] used,Deque<Integer> path,List<List<Integer>> res) {
		if(depth==nums.length) {
			res.add(new ArrayList<>(path));
			return;
		}
		for(int i = 0;i<nums.length;i++) {
		//剪枝条件
			if(i>0&&nums[i]==nums[i-1]&&used[i-1]==false)
				continue;
	    //普通全排列保证这个数没有选过
			if(used[i])
				continue;
			path.addLast(nums[i]);
			used[i] = true;
			dfs(depth+1, nums, used,path,res);
			used[i] = false;
			path.removeLast();
		}
	}

}