子集 II-90

[sl1673495]

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: [1,2,2]
输出:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subsets-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

本题和 组合总和 II-40 的思路类似，剪枝的思路也是和之前相似的，如果循环的时候发现剩余的数字不足以凑成目标长度，就直接剪掉。

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsetsWithDup = function (nums) {
    let n = nums.length
    let res = []
    if (!n) {
        return res
    }

    nums.sort()

    let used = {}

    let helper = (start, prev, target) => {
        if (prev.length === target) {
            let key = genKey(prev)
            if (!used[key]) {
                res.push(prev)
                used[key] = true
            }
            return
        }

        for (let i = start; i < n; i++) {
            let rest = n - i
            let need = target - prev.length
            if (rest < need) {
                continue
            }
            helper(i + 1, prev.concat(nums[i]), target)
        }
    }

    for (let i = 1; i <= n; i++) {
        helper(0, [], i)
    }

    return [[], ...res]
};

function genKey(arr) {
    return arr.join('~')
}