0078. Subsets
=============
题目信息
--------
:题号: 0078. 子集
:难度: Medium
:主题: 回溯、位掩码、迭代扩展、幂集
:原题: `LeetCode 0078 `_
:重点: 从逐个元素二选一,推导到递增下标回溯与迭代倍增
题目重述
--------
给定一个元素互不相同的整数数组 ``nums``,返回由这些元素组成的全部子集。
每个元素在一个子集中最多使用一次。结果必须包含空集与全集,不能出现重复子集,
子集内部顺序和答案整体顺序均不限。
约束如下:
* ``1 <= nums.length <= 10``;
* ``-10 <= nums[i] <= 10``;
* ``nums`` 中所有元素互不相同。
自建示例
--------
.. code-block:: text
输入:nums = [2,5,9]
输出:[[],[2],[5],[9],[2,5],[2,9],[5,9],[2,5,9]]
三个元素分别可以选择或不选择,因此共有 ``2^3 = 8`` 个子集。
.. code-block:: text
输入:nums = [-1,4]
输出:[[],[-1],[4],[-1,4]]
空集同样是合法子集,负数不会改变枚举规则。
.. code-block:: text
输入:nums = [7]
输出:[[],[7]]
单个元素只有不选择与选择两种状态。
C++ 实现
--------
.. code-block:: cpp
#include
#include
class Solution {
private:
std::vector> bitmaskEnumeration(
const std::vector& nums
) {
const int n = static_cast(nums.size());
const int total = 1 << n;
std::vector> result;
result.reserve(total);
for (int mask = 0; mask < total; ++mask) {
std::vector subset;
for (int bit = 0; bit < n; ++bit) {
if ((mask & (1 << bit)) != 0) {
subset.push_back(nums[bit]);
}
}
result.push_back(subset);
}
return result;
}
void binaryDecisionDfs(
const std::vector& nums,
int index,
std::vector& path,
std::vector>& result
) {
if (index == static_cast(nums.size())) {
result.push_back(path);
return;
}
binaryDecisionDfs(nums, index + 1, path, result);
path.push_back(nums[index]);
binaryDecisionDfs(nums, index + 1, path, result);
path.pop_back();
}
std::vector> binaryDecision(
const std::vector& nums
) {
std::vector> result;
std::vector path;
result.reserve(1U << nums.size());
binaryDecisionDfs(nums, 0, path, result);
return result;
}
void increasingIndexDfs(
const std::vector& nums,
int start,
std::vector& path,
std::vector>& result
) {
result.push_back(path);
for (int index = start;
index < static_cast(nums.size());
++index) {
path.push_back(nums[index]);
increasingIndexDfs(nums, index + 1, path, result);
path.pop_back();
}
}
std::vector> increasingIndexBacktracking(
const std::vector& nums
) {
std::vector> result;
std::vector path;
result.reserve(1U << nums.size());
increasingIndexDfs(nums, 0, path, result);
return result;
}
std::vector> iterativeExpansion(
const std::vector& nums
) {
std::vector> result(1);
result.reserve(1U << nums.size());
for (int value : nums) {
const std::size_t old_size = result.size();
for (std::size_t index = 0; index < old_size; ++index) {
std::vector next = result[index];
next.push_back(value);
result.push_back(next);
}
}
return result;
}
public:
std::vector> subsets(std::vector& nums) {
return increasingIndexBacktracking(nums);
}
};
题解
----
二元选择
~~~~~~~~
每个元素只有两种状态:加入子集,或不加入子集。``n`` 个独立的二元选择形成
``2^n`` 个结果,这也是答案数量无法进一步减少的原因。
位掩码直接把第 ``i`` 位解释为是否选择 ``nums[i]``。从 ``0`` 枚举到
``2^n-1``,每个二进制模式都唯一对应一个子集。该方法结构直接,但每个掩码都要重新扫描
全部 ``n`` 个位置。
二叉决策树
~~~~~~~~~~
递归也可直接表达二元选择。处理下标 ``index`` 时,先进入“不选择当前元素”的分支,
再把当前元素加入 ``path``,进入“选择当前元素”的分支。
只有处理完全部元素时才提交路径,因此二叉树的 ``2^n`` 个叶子分别对应全部子集。
选择分支返回后执行 ``pop_back``,恢复父节点的路径状态。
递增下标回溯
~~~~~~~~~~~~
另一种回溯方式把当前路径本身立即视为一个答案,再枚举下一项可以选择的下标。
``start`` 表示下一次选择的最小下标;选择 ``index`` 后递归到 ``index+1``,所以路径中的
输入下标始终严格递增。
空路径在根节点被提交,因此空集自然进入答案。每次增加一个元素后形成的新路径也立即提交,
所以内部节点和叶子节点都会产生子集。
唯一生成
~~~~~~~~
任意子集都有唯一的输入下标递增序列。递增下标回溯只沿这种规范顺序选择元素,
同一个集合不会以不同排列再次生成。
输入元素互不相同,因此不同的下标集合必然对应不同的值集合,无需排序或额外去重结构。
迭代倍增
~~~~~~~~
初始结果只含空集。处理新元素 ``value`` 时,已有子集分成两类:
* 不含 ``value`` 的旧子集;
* 在每个旧子集后加入 ``value`` 得到的新子集。
因此每处理一个元素,结果数量翻倍。循环开始时保存 ``old_size``,只复制本轮之前已经存在的
子集,避免继续遍历刚追加的新子集。
.. list-table::
:header-rows: 1
* - 已处理元素
- 旧子集
- 本轮新增
* - 无
- ``[]``
- 无
* - ``2``
- ``[]``
- ``[2]``
* - ``2,5``
- ``[]``, ``[2]``
- ``[5]``, ``[2,5]``
* - ``2,5,9``
- 前四个子集
- 前四个子集分别加入 ``9``
路径快照
~~~~~~~~
回溯过程始终复用同一个 ``path``。提交答案时必须复制当前内容;随后执行的选择和撤销只修改
工作路径,不会影响已保存的子集。
复杂度
~~~~~~
共有 ``2^n`` 个子集,所有子集包含的元素总数为 ``n * 2^(n-1)``,因此完整输出至少需要
``Theta(n * 2^n)`` 时间与输出空间。
四种方法的时间复杂度均为 ``O(n * 2^n)``。除返回结果外,位掩码和迭代方法的临时子集最长为
``O(n)``;两种递归方法的路径与调用栈为 ``O(n)``。