当前位置：首页 > news >正文

今日算法（回溯子集）

news 2026/6/1 0:13:23

题目描述

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

解题核心思路

这道题是 LeetCode 78「子集」的进阶版，核心难点在于如何在包含重复元素的情况下，生成不重复的子集。

解决重复问题的关键是：

先排序：将数组排序，让相同的元素相邻，方便后续去重判断。
回溯 + 剪枝：在回溯过程中，跳过 “同一层递归中重复元素的选择”，避免生成重复子集。

方法一：回溯法（核心解法）

思路分析

和「子集 I」的回溯思路类似，我们仍然用 “选择 / 不选择” 的方式构建子集，但增加了去重剪枝逻辑：

当我们在同一层递归中，遇到和前一个元素相同的元素时，如果前一个元素没有被选择（即i > startIndex && nums[i] == nums[i-1]），就跳过当前元素，避免重复选择。
这样做的目的是：保证在同一层递归中，相同的元素只会被选择一次，从而避免生成重复的子集。

代码实现（C++）

#include <vector> #include <algorithm> using namespace std; class Solution { private: vector<vector<int>> result; vector<int> path; void backtracking(vector<int>& nums, int startIndex) { // 每次递归都把当前路径加入结果集 result.push_back(path); for (int i = startIndex; i < nums.size(); i++) { // 关键去重逻辑：同一层递归中，跳过和前一个元素相同的元素 if (i > startIndex && nums[i] == nums[i - 1]) { continue; } path.push_back(nums[i]); backtracking(nums, i + 1); path.pop_back(); // 回溯 } } public: vector<vector<int>> subsetsWithDup(vector<int>& nums) { result.clear(); path.clear(); sort(nums.begin(), nums.end()); // 必须先排序，让相同元素相邻 backtracking(nums, 0); return result; } };

复杂度分析

时间复杂度：O (n × 2ⁿ)。虽然有剪枝，但最坏情况下（数组无重复元素），仍需生成 2ⁿ 个子集，每个子集复制到结果集的时间为 O (n)。
空间复杂度：O (n)。递归调用栈的深度为 n，同时path数组最多存储 n 个元素。

方法二：迭代法（增量构造 + 去重）

思路分析

和「子集 I」的迭代思路类似，我们从空集开始，逐步添加元素构建子集。但需要对重复元素做特殊处理：

当遇到重复元素时，只把当前元素添加到 “上一轮新增的子集” 中，而不是所有已有的子集中，避免生成重复子集。
例如nums = [1,2,2]：
1. 初始：[[]]
2. 添加 1：[[], [1]]（新增 1 个子集）
3. 添加 2：[[], [1], [2], [1,2]]（新增 2 个子集）
4. 添加第二个 2：只把 2 添加到上一轮新增的 2 个子集（[2], [1,2]）中，得到[2,2], [1,2,2]，避免重复生成[2], [1,2]。

代码实现（C++）

#include <vector> #include <algorithm> using namespace std; class Solution { public: vector<vector<int>> subsetsWithDup(vector<int>& nums) { vector<vector<int>> result; result.push_back({}); sort(nums.begin(), nums.end()); int start = 0; int size = 0; for (int i = 0; i < nums.size(); i++) { start = 0; // 如果当前元素和前一个元素相同，只从上一轮新增的子集开始添加 if (i > 0 && nums[i] == nums[i - 1]) { start = size; } size = result.size(); // 记录当前结果集的大小，即上一轮新增的子集数量 for (int j = start; j < size; j++) { vector<int> subset = result[j]; subset.push_back(nums[i]); result.push_back(subset); } } return result; } };

复杂度分析

时间复杂度：O (n × 2ⁿ)。最坏情况下（无重复元素），仍需生成 2ⁿ 个子集，每个子集复制时间为 O (n)。
空间复杂度：O (1)。除了结果集之外，只使用了常数级别的额外空间。

两种方法对比

方法	优点	缺点	适用场景
回溯法	思路通用，可扩展到其他组合 / 排列问题，去重逻辑清晰	需要理解递归和剪枝	大多数组合、子集类问题（含重复元素）
迭代法	非递归实现，避免递归栈溢出，逻辑直观	对重复元素的处理需要额外维护索引，代码稍显复杂	数组长度较大，担心递归深度问题的场景

关键知识点总结

排序是前提：只有先将数组排序，相同元素才会相邻，后续的去重逻辑才能生效。
回溯去重的核心：i > startIndex && nums[i] == nums[i-1]这个条件，是为了跳过同一层递归中的重复元素，而不是不同层递归中的重复元素。
迭代法的关键：维护start索引，当遇到重复元素时，只从上一轮新增的子集开始添加当前元素，避免重复生成相同子集。