LeetCode 热题 100 78. 子集

LeetCode 热题 100 | 78. 子集

大家好，今天我们来解决一道经典的算法题——子集。这道题在 LeetCode 上被标记为中等难度，要求给定一个整数数组 nums，返回该数组所有可能的子集（幂集）。解集不能包含重复的子集，你可以按任意顺序返回解集。下面我将详细讲解解题思路，并附上 Python 代码实现。

---

问题描述

给定一个整数数组 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 中的所有元素互不相同

---

解题思路

核心思想

1. 回溯法：

   • 回溯法是一种通过递归枚举所有可能解的方法。
   • 在生成子集的过程中，我们逐个选择数组中的数字，并将其加入当前子集中。
   • 为了避免重复选择同一个数字，我们需要记录哪些数字已经被使用过。

2. 递归终止条件：

   • 每次递归时，当前子集都是一个合法的子集，因此可以直接将其加入结果列表中。

3. 递归过程：

   • 遍历数组中的每个数字，如果该数字尚未被使用，则将其加入当前子集，并标记为已使用。
   • 递归调用生成下一个数字的子集。
   • 在递归返回时，移除当前子集中的最后一个数字，并标记为未使用（回溯）。

---

Python代码实现

class Solution:def subsets(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""result = []path = []def backtracking(start):# 每次递归时，当前子集都是一个合法的子集，直接加入结果列表result.append(path[:])# 遍历数组中的每个数字for i in range(start, len(nums)):path.append(nums[i])  # 将当前数字加入子集backtracking(i + 1)   # 递归生成下一个数字的子集path.pop()            # 回溯：移除当前子集中的最后一个数字backtracking(0)return result# 测试示例
solution = Solution()# 示例 1
nums1 = [1, 2, 3]
print(solution.subsets(nums1))  # 输出: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]# 示例 2
nums2 = [0]
print(solution.subsets(nums2))  # 输出: [[], [0]]

---

代码解析

1. 回溯函数 backtracking：

   • 参数：
     • start：当前递归的起始索引，用于避免重复选择同一个数字。
   • 每次递归时，当前子集 path 都是一个合法的子集，直接将其加入结果列表 result。
   • 遍历数组中的每个数字，从 start 开始，避免重复选择。
   • 将当前数字加入 path，并递归调用生成下一个数字的子集。
   • 在递归返回时，移除 path 中的最后一个数字（回溯）。

2. 结果列表 result：

   • 用于存储所有生成的子集。

3. 路径列表 path：

   • 用于存储当前递归过程中正在构建的子集。

---

复杂度分析

• 时间复杂度：O(2^n)，其中 n 是数组的长度。每个数字有两种选择（加入子集或不加入子集），因此总共有 2^n 种可能的子集。
• 空间复杂度：O(n)，递归调用栈的深度为 n，同时需要存储当前子集 path。

---

示例运行

示例 1

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

示例 2

输入：nums = [0]
输出：[[], [0]]

---

总结

通过回溯法，我们可以高效地生成数组的所有子集。这种方法利用递归枚举所有可能的子集，并通过回溯避免重复选择。希望这篇题解对大家有所帮助，如果有任何问题，欢迎在评论区留言讨论！

关注我，获取更多算法题解和编程技巧！