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

用户头像
Lee Chen
关注
发布于: 1 小时前
LeetCode题解:90. 子集 II,回溯+哈希表去重,JavaScript,详细注释

原题链接: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;
};



发布于: 1 小时前 阅读数: 6
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:90. 子集 II,回溯+哈希表去重,JavaScript,详细注释