# Given a set of distinct integers, nums, return all possible subsets (the power set).
#
# Note: The solution set must not contain duplicate subsets.
#
# For example,
# If nums = [1,2,3], a solution is:
#
# [
# [3],
# [1],
# [2],
# [1,2,3],
# [1,3],
# [2,3],
# [1,2],
# []
# ]
1. 每次对现有子集做一份 拷贝;
2. 从x中选定一个数,后插入 该拷贝中的所有样本 尾部;
3. 将拷贝集 并入 原子集。
DFS:
class Solution():
def subsets(self, x):
if not x:
return [[]]
else:
tmp = self.subsets(x[:-1])
res = tmp + [i+[x[-1]] for i in tmp]
return res
if __name__ == "__main__":
assert Solution().subsets([1, 2, 3]) == [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
迭代:
class Solution():
def subsets(self, x):
res = [[]]
for i in range(len(x)):
for j in range(len(res)):
res.append(res[j]+[x[i]])
return res
if __name__ == "__main__":
assert Solution().subsets([1, 2, 3]) == [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]