Cocolib

Appearance

On this page

子集II ​

Question

给你一个整数数组 nums ，数组中的元素 可能相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

思路 ​

和上一题子集相比，条件变为了数组中的元素 可能相同

需要我们额外的添加一些去重操作

借鉴组合总和II这一题的思路，我们可以使用一个used数组记录已经处理过的元素

去重操作 ​

  • 先给nums排序，使值相同元素相邻
  • 在每一层判断，去重
js
var subsetsWithDup = function(nums) {
    const res = []  // 结果[][]
    const path = [] // 每次递归的结果[]
    const used = []
    res.push([])
    nums.sort((a,b)=>a>b?-1:1)  //排序
    // startIndex ：每次递归的起使位置
    const backtracking = (startIndex)=>{
        for(let i=startIndex;i<nums.length;i++){	// 本层集合中元素
            if(i>0 && nums[i]===nums[i-1] && used[i-1]===0) continue	//去重操作
            path.push(nums[i])				// 处理节点
            used[i]=1
            res.push([...path])
            backtracking(i+1)		// 递归
            path.pop()					//回溯
            used[i]=0
        }
    }
    backtracking(0)
    return res
};