Cocolib

Appearance

On this page

全排列 II ​

Question

给定一个可能包含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

思路 ​

和全排列（不含重复元素）的区别 ​

image-20230617111712770

需要去重，可以参考组合总和II的去重思路：

  • 对nums数组排序
  • 相邻值如果相等不能进入下一层递归
js
var permuteUnique = function(nums) {
    const res = []  // 结果[][]
    const path = [] // 每次递归的结果[]
    // used[] ：记录已经放入path[]中的元素
    nums = nums.sort((a,b)=>a>b?1:-1)  //排序
    const backtracking = (used)=>{
        if(path.length===nums.length){		// 终止条件
            res.push([...path])		// 存放结果
            return
        }
        for(let i= 0 ;i<nums.length;i++){	// 每次从 0 开始
            if(used[i]===1) continue
            if(i>0 && nums[i]===nums[i-1] && used[i-1]===0)    continue //去重
            path.push(nums[i])				// 处理节点 
            used[i]=1
            backtracking(used)		// 递归
            path.pop()					//回溯
            used[i]=0
        }
    }
    backtracking([])
    return res
};