原题链接🔗：子集
难度：中等⭐️⭐️
题目
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
提示：
- 1 <= nums.length <= 10
- -10 <= nums[i] <= 10
- nums 中的所有元素 互不相同
子集(幂集)
子集和幂集是集合论中的两个基本概念。
子集（Subset）：
- 子集是指一个集合的所有元素都属于另一个集合。
- 如果集合A的所有元素都是集合B的元素，那么我们就说A是B的子集，记作 A ⊆ B 。
- 空集（不包含任何元素的集合）是所有集合的子集。
幂集（Power Set）：
- 幂集是指一个集合所有可能子集的集合，包括空集和集合本身。
- 如果集合A的元素个数是n，那么A的幂集将包含 2n 个子集。
- 幂集的元素是原集合的子集，因此幂集的元素数量总是2的幂。
例如，如果有一个集合 A = {1, 2} ，那么：
- 它的子集包括：∅（空集），{1} ，{2}，{1, 2}。
- 它的幂集就是：{∅, {1}, {2}, {1, 2} }。
幂集的大小是原集合大小的2倍，因为每个元素都有“在”或“不在”两种可能性。
题解
- 解题思路：
LeetCode上的“子集”问题是一个经典的算法问题，通常指的是找出给定集合的所有可能子集。这个问题可以通过递归或迭代的方式来解决。下面是解决这个问题的一种通用思路：
递归方法（回溯法） ：递归方法通常使用回溯法来生成所有可能的子集。基本思路如下：
- 初始化：创建一个结果列表
subsets，用来存储所有可能的子集。- 递归函数：定义一个递归函数，该函数接收当前子集
current_subset和当前遍历到的数字索引index。- 递归终止条件：如果
index等于给定集合的长度，将当前子集current_subset添加到结果列表subsets中。- 递归逻辑：
- 不选择当前索引的元素，递归调用
index + 1。- 选择当前索引的元素，将该元素添加到
current_subset中，然后递归调用index + 1。迭代方法（位运算） ：迭代方法使用位运算来生成所有可能的子集。基本思路如下：
- 初始化：创建一个结果列表
subsets，用来存储所有可能的子集。- 循环：从0到2的n次方（n是集合中元素的数量）进行循环，使用二进制表示当前子集的选择状态。
- 位运算：对于每个数字i（从0到2^n-1），使用位运算
(1 << j) & i来检查集合中的第j个元素是否被选中。- 构建子集：根据当前的二进制表示，构建当前子集，并将其添加到结果列表
subsets中。这两种方法各有优缺点，递归方法更直观，但可能会受到递归深度限制；迭代方法不受递归深度限制，但可能在理解上稍微复杂一些。根据具体问题和环境选择合适的方法。
- c++ demo：
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
class Solution {
public:
vector<int> t;
vector<vector<int>> ans;
vector<vector<int>> subsets(vector<int>& nums) {
int n = nums.size();
for (int mask = 0; mask < (1 << n); ++mask) {
t.clear();
for (int i = 0; i < n; ++i) {
if (mask & (1 << i)) {
t.push_back(nums[i]);
}
}
ans.push_back(t);
}
return ans;
}
};
// 示例使用
int main() {
Solution solution;
std::vector<int> nums = { 1, 2 };
std::vector<std::vector<int>> result = solution.subsets(nums);
// 打印所有子集
for (const auto& subset : result) {
for (int num : subset) {
std::cout << num << " ";
}
std::cout << " ";
}
return 0;
}
- 输出结果：
| 1 | 2 | 1 2 |
- 代码仓库地址：subsets
