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

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

思路

  1. 排序 + 迭代 + 去重
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var subsetsWithDup = function (nums) {
  nums.sort((a, b) => a - b)
  const mapper = {}
  let resultItems = [[]]
  for (const val of nums) {
    const nextItems = []
    for (const vals of resultItems) {
      const newVals = [...vals, val]
      const key = newVals.join(',')
      if (!mapper[key]) {
        mapper[key] = true
        nextItems.push(newVals)
      }
    }
    resultItems = resultItems.concat(nextItems)
  }
  return resultItems
}

不去重的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var subsetsWithDup = function (nums) {
  nums.sort((a, b) => a - b)
  let resultItems = [[]]
  let curIndex = 0
  while (curIndex < nums.length) {
    const val = nums[curIndex]
    let sameCount = 1
    while (curIndex + 1 < nums.length && nums[curIndex + 1] === val) {
      ++curIndex
      ++sameCount
    }
    const baseItems = [...resultItems]
    for (let i = 1; i <= sameCount; ++i) {
      resultItems = resultItems.concat(baseItems.map((items) => items.concat(new Array(i).fill(val))))
    }
    ++curIndex
  }
  return resultItems
}