9. 子集II （90）

一、题目内容 中等

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例1：

输入：nums = [1,2,2] 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例2：

输入：nums = [0] 输出：[[],[0]]

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10

  二、解题思路

  这道题，可以学 组合总和 II（40）的思路，来做。
  先对数组进行排序，然后再判断这棵树，

1. 从左到右遍历的过程中，上一个元素是否相同，相同的话不能放入。如果不相同，才可以放入。（不同支）
2. 从上到下遍历的过程中，遇到相同的也可以放入。（同支）

为什么一定要排序，我举个例子：nums = [1,2,3,2,2]，画个图就懂了。

所以需要有一个存储使用过的元素的标志，我们用数组 used 来存储标志。
所谓使用过，分为在同一支和不同支。

1. 我们希望是在不同支情况下，如果也使用过，那么不把 path 计入结果。used[i] = false
2. 同一支的可以，used[i] = true

   如果你问，我想used[i]在不同支的情况下是 true，相同支的情况下是 false 可不可以，当然可以。

for (let i = start; i < nums.length;i++) {
  if (used[i - 1] === false && nums[i] === nums[i - 1]) continue
}

三、具体代码

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsetsWithDup = function (nums) {
  nums.sort((a, b) => a - b)
  const res = []
  const path = []
  const used = [] // used[i] 中 i 代表 nums 的索引，used[i] 代表 nums[i] 是否被使用过
  const len = nums.length
  const backTracking = (start) => {
    res.push(path.map(i => i))
    for (let i = start; i < len; i++) {
      if (used[i - 1] === false && nums[i] === nums[i - 1]) continue
      used[i] = true
      path.push(nums[i])
      backTracking(i + 1)
      path.pop()
      used[i] = false
    }
  }
  backTracking(0)
  return res
};

四、其他解法