leetcode题解78：子集

描述

分析

给定一个集合{1,2,3}，求所有子集，一个容易想到的方法就是递归，比如先把1拿处理，求出{2,3}的所有子集，然后把1加进去；然后2拿出来，求{3}的所有子集；最后剩下把3和空集。

这里有一种更简单的迭代方法；
1. 加入空集{}
2. 上一步生成的所有子集中加入1，新增{1}，现有子集为{}, {1}
3. 上一步生成的所有子集中加入2，新增{2}, {1, 2}，现有子集为{}, {1}, {2}, {1, 2}
4. 上一步生成的所有子集中加入3，新增{3}, {1, 3}, {2, 3}, {1, 2, 3}，现有子集为{}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}

完成，用图表示更清楚

graph TB;
A[''] --> B[''] --> D[''] --> H['']
A[''] --加入1--> C['1'] --> E['1'] --> I['1']
B[''] --加入2--> F['2'] --> J['2']
C['1'] --加入2--> G['1,2'] --> K['1,2']
D[''] --加入3--> L['3']
E['1'] --加入3--> M['1,3']
F['2'] --加入3--> N['2,3']
G['1,2'] --加入3--> O['1,2,3']

代码

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