LC78. 子集

题目描述

给定一个不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。

示例： 输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

思路解析

核心思路：回溯法（深度优先搜索）。遍历数组，每个元素有选或不选两种选择，递归生成所有子集。 关键点： 1. 递归终止条件：遍历完所有元素时，将当前路径加入结果集。 2. 回溯：选择当前元素后递归，递归后撤销选择（回溯）。 3. 注意：空集也是子集，初始时路径为空。 易错点：

• 结果集要包含空集。
• 递归时索引要加1，避免重复使用同一元素。

时间复杂度：O(2^n * n)，每个子集生成需要 O(n) 时间。 空间复杂度：O(n)，递归栈深度和临时路径。