子集 II

[JesseZhao1990]

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsetsWithDup = function(nums) {
    nums = nums.sort((a,b)=>a-b);
    var res = [];
    
    function dfs(nums,arr,i){
        res.push([...arr])
        for(var j=i;j<nums.length;j++){
            arr.push(nums[j]);
            dfs(nums,arr,j+1);
            arr.pop();
            while(nums[j]===nums[j+1]) j++;
        }        
        
    }
    
    dfs(nums,[],0);
    
    return res;
    
};

解题思路

这个题和之前一个题子集非常相似，唯一的不同在于nums可能包含重复元素。

思路和求子集的那个题的思路差不多，唯一的变化是先对nums进行排序，这样剪枝的时候更加方便。只需要关注相邻的两个数是否相等即可。

看下图，除了红色的剪枝，绿色部分的剪枝，就是过滤相邻的相等元素。

LeetCode原题地址：https://leetcode-cn.com/problems/subsets-ii/description/