拓冰网站定制 
题目描述给你一个整数数组nums数组中的元素互不相同。返回该数组所有可能的子集幂集。解集不能包含重复的子集。你可以按任意顺序返回解集。示例 1输入nums [1,2,3]输出[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]示例 2输入nums [0]输出[[],[0]]解题思路方法一回溯 start 参数核心思路把问题看成树形结构每个节点都是一个子集从start开始遍历避免重复每个节点都收集结果不是只有叶子节点具体过程示例nums [1,2,3][] ← 收集 / | \ [1] [2] [3] ← 收集 / \ | [1,2] [1,3] [2,3] ← 收集 | [1,2,3] ← 收集 所有子集: [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]代码实现class Solution { public: vectorvectorint subsets(vectorint nums) { vectorvectorint result; vectorint path; backtrack(nums, 0, path, result); return result; } private: void backtrack(vectorint nums, int start, vectorint path, vectorvectorint result) { // 每个节点都收集结果不是只有叶子节点 result.push_back(path); // 从 start 开始遍历避免重复子集 for (int i start; i nums.size(); i) { path.push_back(nums[i]); // 选择 backtrack(nums, i 1, path, result); // 递归传 i1 path.pop_back(); // 撤销 } } };复杂度分析设n是数组长度。维度复杂度说明时间复杂度O(n × 2^n)2^n 个子集每个子集平均长度 n/2空间复杂度O(n)递归栈深度 path 长度关键细节1. 为什么每个节点都收集结果因为每个节点都是一个子集不只是叶子节点。比如[1]是子集[1,2]也是子集。2. 为什么用start参数start控制当前层从哪个位置开始遍历避免产生重复子集。例子nums [1,2,3]选了1后下一层从2开始i1不会选1之前的所以不会出现[2,1]这种重复子集3. 为什么递归时传i1而不是i传i1不重复选当前元素子集问题每个元素只能选一次传i允许重复选组合总和问题4. 和「全排列」的区别题目区别46. 全排列顺序重要用used标记78. 子集顺序不重要用start控制方法二位运算二进制枚举思路用n位二进制数表示每个元素选或不选。代码实现class Solution { public: vectorvectorint subsets(vectorint nums) { int n nums.size(); vectorvectorint result; for (int mask 0; mask (1 n); mask) { vectorint subset; for (int i 0; i n; i) { if (mask (1 i)) { subset.push_back(nums[i]); } } result.push_back(subset); } return result; } };复杂度时间 O(n × 2^n)空间 O(n × 2^n)优点不需要递归代码简洁。缺点只能处理n ≤ 20的情况2^n太大。方法三迭代法逐个添加思路从空集开始每次把新元素加入已有子集。代码实现class Solution { public: vectorvectorint subsets(vectorint nums) { vectorvectorint result {{}}; for (int num : nums) { int size result.size(); for (int i 0; i size; i) { vectorint subset result[i]; subset.push_back(num); result.push_back(subset); } } return result; } };复杂度时间 O(n × 2^n)空间 O(n × 2^n)三种方法对比方法时间复杂度空间复杂度推荐度回溯 startO(n × 2^n)O(n)⭐⭐⭐⭐⭐位运算O(n × 2^n)O(n × 2^n)⭐⭐⭐⭐迭代法O(n × 2^n)O(n × 2^n)⭐⭐⭐⭐总结要点说明核心思想回溯每个节点收集结果从 start 开始遍历关键操作result.push_back(path)放在递归开头终止条件没有显式终止条件遍历完自然结束时间复杂度O(n × 2^n)空间复杂度O(n) 【回溯-5】78.子集
题目描述给你一个整数数组nums数组中的元素互不相同。返回该数组所有可能的子集幂集。解集不能包含重复的子集。你可以按任意顺序返回解集。示例 1输入nums [1,2,3]输出[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]示例 2输入nums [0]输出[[],[0]]解题思路方法一回溯 start 参数核心思路把问题看成树形结构每个节点都是一个子集从start开始遍历避免重复每个节点都收集结果不是只有叶子节点具体过程示例nums [1,2,3][] ← 收集 / | \ [1] [2] [3] ← 收集 / \ | [1,2] [1,3] [2,3] ← 收集 | [1,2,3] ← 收集 所有子集: [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]代码实现class Solution { public: vectorvectorint subsets(vectorint nums) { vectorvectorint result; vectorint path; backtrack(nums, 0, path, result); return result; } private: void backtrack(vectorint nums, int start, vectorint path, vectorvectorint result) { // 每个节点都收集结果不是只有叶子节点 result.push_back(path); // 从 start 开始遍历避免重复子集 for (int i start; i nums.size(); i) { path.push_back(nums[i]); // 选择 backtrack(nums, i 1, path, result); // 递归传 i1 path.pop_back(); // 撤销 } } };复杂度分析设n是数组长度。维度复杂度说明时间复杂度O(n × 2^n)2^n 个子集每个子集平均长度 n/2空间复杂度O(n)递归栈深度 path 长度关键细节1. 为什么每个节点都收集结果因为每个节点都是一个子集不只是叶子节点。比如[1]是子集[1,2]也是子集。2. 为什么用start参数start控制当前层从哪个位置开始遍历避免产生重复子集。例子nums [1,2,3]选了1后下一层从2开始i1不会选1之前的所以不会出现[2,1]这种重复子集3. 为什么递归时传i1而不是i传i1不重复选当前元素子集问题每个元素只能选一次传i允许重复选组合总和问题4. 和「全排列」的区别题目区别46. 全排列顺序重要用used标记78. 子集顺序不重要用start控制方法二位运算二进制枚举思路用n位二进制数表示每个元素选或不选。代码实现class Solution { public: vectorvectorint subsets(vectorint nums) { int n nums.size(); vectorvectorint result; for (int mask 0; mask (1 n); mask) { vectorint subset; for (int i 0; i n; i) { if (mask (1 i)) { subset.push_back(nums[i]); } } result.push_back(subset); } return result; } };复杂度时间 O(n × 2^n)空间 O(n × 2^n)优点不需要递归代码简洁。缺点只能处理n ≤ 20的情况2^n太大。方法三迭代法逐个添加思路从空集开始每次把新元素加入已有子集。代码实现class Solution { public: vectorvectorint subsets(vectorint nums) { vectorvectorint result {{}}; for (int num : nums) { int size result.size(); for (int i 0; i size; i) { vectorint subset result[i]; subset.push_back(num); result.push_back(subset); } } return result; } };复杂度时间 O(n × 2^n)空间 O(n × 2^n)三种方法对比方法时间复杂度空间复杂度推荐度回溯 startO(n × 2^n)O(n)⭐⭐⭐⭐⭐位运算O(n × 2^n)O(n × 2^n)⭐⭐⭐⭐迭代法O(n × 2^n)O(n × 2^n)⭐⭐⭐⭐总结要点说明核心思想回溯每个节点收集结果从 start 开始遍历关键操作result.push_back(path)放在递归开头终止条件没有显式终止条件遍历完自然结束时间复杂度O(n × 2^n)空间复杂度O(n)