全排列II（LeetCode 47）
一、题目描述
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
提示：
1 <= nums.length <= 8-10 <= nums[i] <= 10
二、题目解析
三、参考代码
1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
// 排序（升序或者降序都可以），排序是剪枝的前提
Arrays.sort(nums);
// 结果集合
List<List<Integer>> sets = new ArrayList<List<Integer>>();
// 每次的子集
List<Integer> path = new ArrayList<Integer>();
Boolean[] used = new Boolean[nums.length];
// 每个元素默认一开始都没有被选择
Arrays.fill(used, false);
// 执行回溯算法
backtrack( nums , path,used , sets);
// 返回结果
return sets;
}
// used 表示递归时正在访问的数组元素是否之前已经被访问过
// nums 表示当前集合中的元素
// path 表示每次递归后生成的子集
// sets 表示最终生成的所有子集合
private void backtrack( int[] nums , List<Integer> path , Boolean[] used , List<List<Integer>> sets ){
// 2、寻找结束条件，由于回溯算法是借助递归实现，所以也就是去寻找递归终止条件
if( path.size() == nums.length){
// 每次确定好一个子集，都把它加入到结果集合中
sets.add(new ArrayList<Integer>(path));
return;
}
for( int i = 0 ; i < nums.length ; i++ ){
if(!used[i]){
if( i > 0 && nums[i] == nums[i - 1] && !used[i-1]){
continue;
}
// 把本次递归访问的元素加入到 subset 数组中
path.add(nums[i]);
used[i] = true;
// 4、判断是否需要剪枝，去判断此时存储的数据是否之前已经被存储过
// 本题不需要剪枝
// 5、做出选择，递归调用该函数，进入下一层继续搜索
// 递归
backtrack( nums , path ,used, sets);
// 6、撤销选择，回到上一层的状态
// 取消对 nums[i] 的选择
used[i] = false;
path.remove(path.size() - 1);
}
}
}
}
2、C++ 代码
3、Python 代码
