LeetCode题解：90. 子集 II，回溯+哈希表去重，JavaScript，详细注释

[chencl1986]

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

解题思路：

1. 使用DFS生成所有可能的排列情况。
2. 所有的子集包括nums中的每个元素包含于不包含两种状态。
3. 可以在递归下探到下一层之前，利用当前元素存入或不存入subset的状态进行区分。
4. 每个子集存入result时，将其保存在Set中，下次遇到该子集时即可跳过，以此实现去重。

function dfs(nums, subset, result, set, current) {
  // 当current等于nums.length时，表示子集已经生成
  if (current === nums.length) {
    // 判断Set中是否已存储过该子集，如果是，则表示该子集已重复，不需要存储到result
    if (!set.has(JSON.stringify(subset))) {
      result.push(subset.slice()); // 存储子集到result
      set.add(JSON.stringify(subset)); // 标识该子集已经储存过
    }
    // 终止递归
    return;
  }

  // 当前层递归逻辑
  // 每层递归有两种结果，即是否存入元素
  // 将当前索引的元素存入subset
  subset.push(nums[current]);
  // 下一个子集元素所用的索引
  const newCurrent = current + 1;

  // 保持当前元素被存储的状态，下探到下一层递归
  dfs(nums, subset, result, set, newCurrent);

  // 清理当前层状态
  // 将当前层存入subset的元素弹出。
  // 即表示不存入当前元素的子集。
  subset.pop();

  // 保持当前元素没有被存储的状态，下探到下一层递归
  dfs(nums, subset, result, set, newCurrent);
}
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsetsWithDup = function (nums) {
  let result = []; // 存储最终结果
  let subset = []; // 存储各个子集
  let set = new Set(); // 使用Set去重
  nums.sort((a, b) => a - b); // 将nums排序，保证能够有效去重
  // 递归生成所有可能子集，再使用Set去重得到不重复的子集
  dfs(nums, subset, result, set, 0);
  return result;
};