学习记录：js算法（八十四）：子集 II
文章目录
- 子集 II
- 思路一
- 思路二
子集 II
给你一个整数数组
nums，其中可能包含重复元素，请你返回该数组所有可能的
子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
思路一
function subsetsWithDup(nums) {
nums.sort((a, b) => a - b); // 先排序
const result = [];
const backtrack = (start, path, lastSelected = -1) => {
// 将当前子集添加到结果集中
result.push([...path]);
for (let i = start; i < nums.length; i++) {
// 跳过重复元素
if (i > start && nums[i] === nums[i - 1] && lastSelected !== i - 1) continue;
// 选择当前元素
path.push(nums[i]);
backtrack(i + 1, path, i); // 注意传递当前元素的下标
// 回溯，撤销选择
path.pop();
}
};
backtrack(0, []);
return result;
}
讲解
要解决这个问题，我们可以基于之前提到的回溯算法思路进行扩展，以处理包含重复元素的情况。关键在于，在递归过程中增加一个判断条件来跳过已经处理过的重复元素，以避免生成重复的子集。
- 排序数组：首先对原数组进行排序，这样相同的元素会被排列在一起，便于我们在递归过程中跳过重复的元素。
- 定义递归函数：递归函数需要接收当前子集、当前遍历到的数组下标以及上一个被选中元素的下标作为参数。
- 递归终止条件：当遍历到数组末尾时，将当前子集添加到结果集中，然后返回。
- 单层递归逻辑：
○ 如果当前元素与前一个被选中元素相同，并且前一个元素没有被选中，则跳过当前元素（避免生成重复子集）。
○ 将当前元素加入子集，然后递归调用下一个元素。
○ 回溯：从子集中移除当前元素（即不选择当前元素），然后递归调用下一个元素。
思路二
var subsetsWithDup = function (nums) {
const result = [];
const n = nums.length;
nums.sort((a, b) => a - b); // 先对数组进行排序
const totalSubsets = 1 << n; // 2^n
const seen = new Set(); // 用于去重
for (let i = 0; i < totalSubsets; i++) {
const subset = [];
for (let j = 0; j < n; j++) {
if (i & (1 << j)) { // 检查第 j 位是否为 1
subset.push(nums[j]);
}
}
// 将子集转换为字符串形式以便于去重
const subsetStr = subset.join(',');
if (!seen.has(subsetStr)) {
seen.add(subsetStr);
result.push(subset);
}
}
return result;
};
讲解
- 函数定义
subsetsWithDup是一个用于生成包含重复元素的数组的所有子集的函数。它接受一个整数数组nums作为参数。- 初始化
函数开始时，定义一个空数组result用于存储所有生成的子集，并获取数组nums的长度n。- 排序
在生成子集之前，首先对数组nums进行排序。排序的目的是为了确保相同的元素是相邻的，这样在后续处理时能够方便地去重。- 计算总子集数
接下来，计算总的子集数量，这个数量为2^n。使用左移运算符1 << n来实现这一点。这个计算表明，对于n个元素，我们有2^n种可能的子集组合。- 去重集合
定义一个集合seen，用于存储已经生成的子集，以避免重复的子集被添加到结果中。- 遍历所有可能的子集
使用一个循环，从0到totalSubsets - 1遍历所有可能的子集。每次循环开始时，初始化一个空数组subset用于存储当前生成的子集。- 生成子集
在内部的循环中，遍历从0到n - 1的每个元素。通过位运算检查当前循环变量i的每一位是否为1。如果某一位为1，则将对应的元素nums[j]添加到当前子集subset中。- 转换和去重
生成当前子集后，将其转换为字符串形式，以便于在集合中进行去重。通过join(',')方法将subset数组的元素连接成一个字符串。接下来，检查该字符串是否已经存在于seen集合中。如果不存在，则将其添加到seen集合中，并将当前子集subset添加到结果数组result中。- 返回结果
最后，函数返回结果数组result，其中包含所有唯一的子集。