0078.子集

题目链接78. 子集 - 力扣LeetCode题目描述给你一个整数数组nums数组中的元素 互不相同 。返回该数组所有可能的子集幂集。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。题目示例示例 1 :输入nums [1,2,3] 输出[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]示例 2 :输入nums [0] 输出[[],[0]]解题思路题目要求生成给定数组的所有可能子集包括空集。通过回溯算法在每一步选择是否包含当前元素递归生成所有可能的组合。题解代码classSolution{privatefinalListListIntegeransnewArrayList();// 存储所有子集的结果列表privatefinalListIntegerpathnewArrayList();// 当前递归路径当前子集privateint[]nums;// 输入数组publicListListIntegersubsets(int[]nums){this.numsnums;// 初始化输入数组dfs(0);// 从第0个元素开始递归returnans;}// 回溯函数处理第i个元素的选择与不选privatevoiddfs(inti){if(inums.length){// 所有元素处理完毕ans.add(newArrayList(path));// 将当前路径拷贝到结果列表return;}// 不选当前元素nums[i]dfs(i1);// 直接递归处理下一个元素// 选当前元素nums[i]path.add(nums[i]);// 将当前元素加入路径dfs(i1);// 递归处理下一个元素path.remove(path.size()-1);// 回溯移除最后添加的元素恢复现场}}复杂度分析时间复杂度O(n × 2ⁿ)每个元素有选/不选两种可能总共有2ⁿ个子集。每个子集被复制到结果列表需要O(n)时间总时间复杂度为O(n × 2ⁿ)。空间复杂度O(n × 2ⁿ)结果列表存储2ⁿ个子集每个子集平均长度为n/2。递归调用栈深度为O(n)。