LeetCode题解：90. 子集 II，迭代，JavaScript，详细注释

[chencl1986]

原题链接：https://leetcode-cn.com/problems/subsets-ii/

解题思路：

1. 生成所有子集，实际上要达到的效果是，nums中的每个元素是否显示在子集中。
2. 假设现在已经生成了n-1个元素的子集，当前遍历到第n个元素，那么只需要将现有的子集遍历一次，将第n个元素加入到现有子集中，形成新的子集即可。
3. 如何去重：
   • 关于去重的方法，可以参考题解详细通俗的思路分析，多解法中的迭代法部分，结合我的注释加深理解。
   • 如果在不去重的情况下，观察[1, 2, 2]的所有子集如下：

数组 [ 1 2 2 ] 
[ ] 的所有子集 [ ]
[ 1 ] 的所有子集 [ ] [ 1 ] 
[ 1 2 ] 的所有子集 [ ] [ 1 ] [ 2 ][ 1 2 ]
[ 1 2 2 ] 的所有子集 [ ] [ 1 ] [ 2 ] [ 1 2 ] [ 2 ] [ 1 2 ] [ 2 2 ] [ 1 2 2 ] 

会发现[ 1 2 2 ] 的所有子串 [ ] [ 1 ] [ 2 ] [ 1 2 ] [ 2 ] [ 1 2 ] [ 2 2 ] [ 1 2 2 ] 中，重复的子集是[ 2 ] [ 1 2 ]，而它们是由[ 1 ] 的所有子集 [ ] [ 1 ] 分别加上2得到的。
因此我们要做的是，在输出[ 1 2 2 ]的子集时，排除掉[ 1 ]的子集。
具体做法就是先保存[ 1 ]的所有子集长度，然后在第二层遍历中排除掉这部分子集。
同时需要判断nums[i] === nums[i - 1]，也就是当出现重复元素时，才进行去重，
因为第一次遍历该元素时，已经输出过一次子集。

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsetsWithDup = function (nums) {
  // 储存结果的数组
  // 初始状态要含有一个空数组，即无任何元素的子集
  // 空数组的存在是为了开启第二层循环
  let result = [[]]; // 存储最终结果
  let lastTwoResultLength = 0; // 存储上上次的子集数量
  nums.sort((a, b) => a - b); // 将nums排序，保证能够有效去重

  // 每次从nums中取出一个元素，作为新子集的元素
  for (let i = 0; i < nums.length; i++) {
    // 获取当前的子集数量进行遍历，避免循环过程中result长度不断变化
    let resultLength = result.length;

    // 在现有子集的基础上，添加当前元素，生成新的子集
    for (let j = 0; j < resultLength; j++) {
      if (
        // 当不是第一次遇到该元素时，才进行去重
        nums[i] === nums[i - 1] &&
        // 过滤掉上一次已经重复输出过子集 的情况
        j < lastTwoResultLength) {
        // 跳过当前元素，继续输出下一种 元素的子集
        continue;
      }
      result.push([...result[j], nums[i]]);
    }

    // 存储上一次的子集数量
    lastTwoResultLength = resultLength;
  }

  return result;
};