78.子集

backtracking, https://leetcode.cn/problems/subsets/

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

思路：递归回溯（选或不选）

对每个元素有两种选择：选入子集 或 不选入子集。递归遍历所有位置，到达末尾时将当前路径加入结果。

python

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        ans, sol = [], []
        
        def backtrack(i):
            # 终止条件：处理完所有元素
            if i == n:
                ans.append(sol[:])
                return
            
            # 分支1：不选择 nums[i]
            backtrack(i + 1)
            
            # 分支2：选择 nums[i]
            sol.append(nums[i])
            backtrack(i + 1)
            sol.pop()  # 回溯
        
        backtrack(0)
        return ans

子集视频讲解：https://pku.instructuremedia.com/embed/d8ccd717-3664-41bc-85d2-7170f348327b

总结对比（ 46.全排列，79.子集）

问题	决策方式	终止条件	是否需要去重	时间复杂度
全排列	从剩余元素中选择	路径长度 = n	是（避免重复使用）	$O (n \times n!)$
子集	每个元素选/不选	索引到达数组末尾	否（天然无重）	$O (2^{n} \times n)$

⚠️ 注意：由于每次添加路径都需要复制 sol[:]，因此总时间复杂度中乘以 n。

python

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        result = []
        ans = []
        def dfs(x):
            if x == n:
                result.append(ans[:])
                return
            dfs(x + 1)
            ans.append(nums[x])
            dfs(x + 1)
            ans.pop()
        dfs(0)
        return result

python

from typing import List
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []

        def backtrack(start, path):
            ans.append(path)
            for i in range(start, len(nums)):
                backtrack(i+1, path+[nums[i]])
        backtrack(0, []) # start with an empty path
        return ans

if __name__ == "__main__":
    nums = [1,2,3]
    print(Solution().subsets(nums))

关键部分解读
回溯函数 backtrack:
python
def backtrack(start, path):
    ans.append(path)  # 1. 将当前路径(子集)加入结果
    for i in range(start, len(nums)):  # 2. 从start开始遍历数组
        backtrack(i+1, path+[nums[i]])  # 3. 递归调用
start 参数表示当前应该从哪个索引开始处理
path 参数表示当前已经构建的子集
回溯过程:
每次调用 backtrack 都会先将当前 path 加入结果列表 ans
然后从 start 位置开始遍历数组中的元素
对于每个元素，递归调用 backtrack，参数更新为：
i+1：确保不重复使用同一个元素
path+[nums[i]]：将当前元素加入子集
初始调用:
python
backtrack(0, [])  # 从空路径开始，处理索引0
示例运行
对于输入 [1,2,3]，程序会生成以下子集：
[],        # 初始空集
[1],      # 包含1的子集
[1,2],    # 包含1,2的子集
[1,2,3],  # 包含1,2,3的子集
[1,3],    # 包含1,3的子集
[2],      # 包含2的子集
[2,3],    # 包含2,3的子集
[3]       # 包含3的子集
回溯算法特点
使用递归来实现深度优先搜索
通过 start 参数避免重复的子集
每次递归都生成一个新的子集加入结果
时间复杂度为 $O (2^{n})$ ，因为一个有n个元素的集合有2^n个子集
这个实现简洁高效，是解决子集问题的经典回溯方法。

陈冠宇 24工学院

突发奇想搞了个二进制数和子集的一一对应

python

from typing import List

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)            # 数组长度
        ans = []                 # 存储所有子集的结果
        for i in range(0, 2**n): # 遍历所有可能的子集（共2^n个）
            cur = []             # 当前子集
            prev = f'{i:0{n}b}'   # 将i转为n位二进制字符串（补前导0）
            for j in range(n):   # 检查每一位是否为1
                if prev[j] == '1':
                    cur.append(nums[j])  # 包含对应元素
            ans.append(cur)      # 将当前子集加入结果
        return ans

python

# 曾孜博 24工学院
class Solution:
    from collections import defaultdict
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans=[[]]
        for x in nums:
            ans+=[[x] + y for y in ans]
        return ans

参考了灵神的题解对代码进行了优化。这道题的思路和寒假pre中的01321棋盘问题是一样的，与八皇后有一定差别。八皇后考虑的是每一个数字都要选，而这道题的每一个数字则有两种选择：选或者不选。那么普通的dfs一次对应的就是“选择该元素”，然后在dfs结束后并把这个元素pop掉，紧接着对下一个元素进行第二次dfs，对应的就是“不选该元素”。然后考虑到原数组可能存在重复值，使用while循环将索引k不断右移到新元素进行第二次dfs（题目是90-子集II）

python

# 汤伟杰，信息管理系
class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        def dfs(nums,curr,k,ans):
            if k==len(nums):
               ans.append(curr[:])
               return 

            num = nums[k]
            curr.append(num)
            dfs(nums, curr, k+1, ans)
            curr.pop()

            while k<len(nums) and num == nums[k]:
                k+=1
            dfs(nums, curr, k, ans) 

        ans=[]
        nums.sort()
        dfs(nums,[],0,ans)
        return ans

python

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        return [[nums[i] for i in range(len(nums)) if musk & 1 << i] for musk in range(1 << len(nums))]

解读：生成子集的位运算解法
这段代码是一个Python类方法，用于生成给定整数列表的所有可能子集。它使用了位运算的技巧来高效地生成所有子集。
工作原理
子集总数：对于一个长度为n的列表，子集总数是2^n个（包括空集）。1 << len(nums)计算这个总数（2的n次方）。
位掩码(mask)表示：
每个mask代表一个子集的选择方式
mask的二进制表示中，第i位为1表示选择nums[i]，为0表示不选择
列表推导式：
外层推导式遍历所有可能的mask值（0到2^n-1）
内层推导式检查mask的每一位，确定哪些元素应该包含在当前子集中
示例
以nums = [1,2,3]为例：
len(nums) = 3 → 总子集数=8 (0b000到0b111)
mask从0(0b000)到7(0b111)：
0(0b000): [] (空集)
1(0b001): [1]
2(0b010): [2]
3(0b011): [1,2]
...
7(0b111): [1,2,3]
优点
高效：利用位运算快速生成所有子集
简洁：一行代码实现复杂功能
通用：适用于任何长度的输入列表
注意事项
当nums长度较大时（如超过20），子集数量会非常大(2^20=1,048,576)，可能导致内存问题
返回的子集顺序是按二进制掩码顺序排列的，不是按子集大小排序的
这种方法是解决子集问题的经典位运算解法，展示了Python列表推导式和位运算的强大结合。

【赵凌哲、光华管理学院】枚举选出来的数字组合。用时3分钟。

python

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []
        for i in range(2**len(nums)):
            now = i
            lst = []
            for j in range(len(nums)):
                if now & 1:
                    lst.append(nums[j])
                now >>= 1
            ans.append(lst)
        return ans

思路：有动态规划

python

 
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        ans = [[]]
        for i in range(n):
            for j in range(len(ans)):
                ans.append(ans[j] + [nums[i]])
        return ans

78.子集 ​

78.子集