【算法】子集II

难度：中等

题目：

给你一个整数数组 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

解题思路：

要解决这个问题，我们可以基于之前提到的回溯算法思路进行扩展，以处理包含重复元素的情况。关键在于，在递归过程中增加一个判断条件来跳过已经处理过的重复元素，以避免生成重复的子集。
1、排序数组：首先对原数组进行排序，这样相同的元素会被排列在一起，便于我们在递归过程中跳过重复的元素。
2、定义递归函数：递归函数需要接收当前子集、当前遍历到的数组下标以及上一个被选中元素的下标作为参数。
3、递归终止条件：当遍历到数组末尾时，将当前子集添加到结果集中，然后返回。
4、 单层递归逻辑：

• 如果当前元素与前一个被选中元素相同，并且前一个元素没有被选中，则跳过当前元素（避免生成重复子集）。
• 将当前元素加入子集，然后递归调用下一个元素。
• 回溯：从子集中移除当前元素（即不选择当前元素），然后递归调用下一个元素。

JavaScript 实现：

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;
}

// 示例
const nums = [1, 2, 2];
console.log(subsetsWithDup(nums)); // 输出所有不重复的子集

这段代码首先对输入数组nums进行了排序，然后定义了subsetsWithDup函数来处理含有重复元素的子集问题。在backtrack函数中，增加了判断条件来避免处理重复元素，确保最终结果中不会有重复的子集。最后，返回所有可能的子集（幂集）。

原文地址：https://blog.csdn.net/xiaolinlife/article/details/140642469

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！