给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutations-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这个关键在于剪纸，剪纸的关键在于used[i - 1]=false && nums[i] == nums[i - 1]，因为这时我们刚剪纸回溯，必然直接去掉，但是不是==就要去掉，因为还有第一次路径的写入。
class Solution { public List<List<Integer>> permuteUnique(int[] nums) { int len = nums.length; List<List<Integer>> res = new ArrayList<>(); if (len == 0) { return res; } Arrays.sort(nums); boolean[] used = new boolean[len]; Deque<Integer> path = new ArrayDeque<>(); dfs(nums, len, 0, used, path, res); return res; } public void dfs(int[] nums, int len, int depth, boolean[] used, Deque<Integer> path, List<List<Integer>> res) { if (depth == len) { res.add(new ArrayList<>(path)); return; } for (int i = 0; i < len; i++) { if (used[i]) { continue; } if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) { continue; } path.addLast(nums[i]); used[i] = true; dfs(nums, len, depth + 1, used, path, res); used[i] = false; path.removeLast(); } } }
end
原文：https://www.cnblogs.com/CherryTab/p/12380616.html