题目描述给你一个整数数组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] 10nums中的所有元素互不相同解题思路子集问题是回溯算法的经典入门题目同时也可以用位运算和迭代法来解决。下面我们将详细讲解这三种方法。方法一回溯法思路分析回溯法的核心思想是 选择与不选择。对于数组中的每一个元素我们都有两种选择包含它或者不包含它。通过递归遍历所有可能的选择我们就能得到所有的子集。具体来说我们可以维护一个当前的子集path然后从数组的第一个元素开始不选择当前元素直接递归处理下一个元素选择当前元素将其加入path然后递归处理下一个元素递归返回后将当前元素从path中移除回溯当我们处理完所有元素时就将当前的path加入结果集。代码实现C#include vector using namespace std; class Solution { private: vectorvectorint result; // 存储所有子集 vectorint path; // 存储当前子集 void backtracking(vectorint nums, int startIndex) { // 将当前子集加入结果集 result.push_back(path); // 从startIndex开始遍历避免重复子集 for (int i startIndex; i nums.size(); i) { path.push_back(nums[i]); // 选择当前元素 backtracking(nums, i 1); // 递归处理下一个元素 path.pop_back(); // 回溯撤销选择 } } public: vectorvectorint subsets(vectorint nums) { result.clear(); path.clear(); backtracking(nums, 0); return result; } };复杂度分析时间复杂度O (n × 2ⁿ)。共有 2ⁿ 个子集每个子集需要 O (n) 的时间来复制到结果集中。空间复杂度O (n)。递归调用栈的深度为 n同时path数组最多存储 n 个元素。方法二位运算法思路分析对于一个长度为 n 的数组它的子集总数是 2ⁿ 个。我们可以用一个 n 位的二进制数来表示一个子集其中每一位表示对应位置的元素是否被包含在子集中。例如对于数组[1,2,3]二进制000表示空集[]二进制001表示子集[1]二进制010表示子集[2]二进制011表示子集[1,2]以此类推直到111表示子集[1,2,3]我们只需要遍历从 0 到 2ⁿ - 1 的所有整数然后根据每个整数的二进制表示来构造对应的子集即可。代码实现C#include vector using namespace std; class Solution { public: vectorvectorint subsets(vectorint nums) { vectorvectorint result; int n nums.size(); int total 1 n; // 2^n 个子集 for (int mask 0; mask total; mask) { vectorint subset; for (int i 0; i n; i) { // 检查第i位是否为1 if (mask (1 i)) { subset.push_back(nums[i]); } } result.push_back(subset); } return result; } };复杂度分析时间复杂度O (n × 2ⁿ)。共有 2ⁿ 个子集每个子集需要 O (n) 的时间来构造。空间复杂度O (1)。除了结果集之外只使用了常数级别的额外空间。方法三迭代法思路分析迭代法的核心思想是 逐步构建。我们从空集开始然后依次将数组中的每个元素添加到已有的所有子集中从而生成新的子集。例如对于数组[1,2,3]初始状态[[]]添加元素 1将 1 添加到已有的每个子集中得到[[], [1]]添加元素 2将 2 添加到已有的每个子集中得到[[], [1], [2], [1,2]]添加元素 3将 3 添加到已有的每个子集中得到最终结果代码实现C#include vector using namespace std; class Solution { public: vectorvectorint subsets(vectorint nums) { vectorvectorint result; result.push_back({}); // 初始化为包含空集 for (int num : nums) { // 保存当前结果集的大小避免在循环中修改result导致无限循环 int size result.size(); for (int i 0; i size; i) { // 复制已有子集并添加当前元素 vectorint newSubset result[i]; newSubset.push_back(num); result.push_back(newSubset); } } return result; } };复杂度分析时间复杂度O (n × 2ⁿ)。共有 2ⁿ 个子集每个子集需要 O (n) 的时间来复制。空间复杂度O (1)。除了结果集之外只使用了常数级别的额外空间。三种方法对比表格方法优点缺点适用场景回溯法思路清晰易于理解可扩展到有重复元素的子集问题需要理解递归和回溯的概念大多数子集、组合、排列问题位运算法代码简洁效率高不需要递归思路相对抽象数组长度较小n ≤ 20的情况迭代法直观易懂不需要递归代码稍长初学者理解子集生成过程总结子集问题是算法中的基础问题掌握这三种解法对于理解回溯算法、位运算和迭代思想都有很大帮助。回溯法是解决组合类问题的通用方法需要重点掌握 选择 - 递归 - 回溯 的思想位运算法利用了二进制的特性代码非常简洁在数组长度较小时效率很高迭代法通过逐步构建的方式生成子集最容易理解在实际解题中推荐优先掌握回溯法因为它可以很容易地扩展到其他类似问题如 子集 II数组中有重复元素、组合总和 等。