文章目录
- 题目描述
- 法一(巧妙暴力解)
- 思路分析
- 完整代码
- 法二(回溯):
- 思路分析
- 完整代码
题目描述
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]示例 2：
输入：nums = [0]
输出：[[],[0]]
法一(巧妙暴力解)
思路分析
这道题上来一眼思路肯定就是暴力啊，要不是为了练回溯，谁这道题会用回溯解啊，真的是。
而且巧妙暴力比回溯要快一点，虽然回溯也是一种暴力吧。
看一下 前两个是回溯，后两个是巧妙暴力，虽然力扣上这个时间有时候会抽风，不过大体上对比可以参考一下的。
说一下巧妙暴力算法
思路就是，每次遍历一个元素，都让当前答案集里的每一个集合都加上这个元素，再放入答案集。
来个例子，比如num = [1,2,3] 答案集res = [[]]。
- 当前答案集合res里只有一个空集 []。
- 遍历到1的时候，res里的空集加上1，再加入答案集，此时res= [[],[1]]
- 遍历到2的时候，res里的所有子集都加上2，再加入答案集,此时res = [[],[1],[2],[1,2]]
- 遍历到3的时候，同理，此时res = [[],[1],[2],[1,2],[3],[1,3],[1,2,3]]
完整代码
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = [[]]
for i in range(len(nums)):
for j in res[:]:
res.append(j+[nums[i]])
print(res)
return res
法二(回溯):
思路分析
正经解法还是得学的。
这道题对比前几个回溯的题，明显简单了一些，就是终止条件那块稍微变动了一下，这算是回溯的另一个小块，前面是组合和分割，这个算是集合 子集的一个小分支吧。
老规矩 回溯三步法：
1.确定函数参数;
这个没什么可说的，这道题比较清晰，就只有一个回溯中常用的startindex了。
2.确定终止条件：
这道题和前面不同的唯一的地方就是这个终止条件，可以老规矩画树出来看看，实际上在本题下，树上的每一个节点都要收集，所以说这道题没有终止条件，只要循环体for循环完成就行了。
3.循环体：
这题就是最基础的哪一种，毫无变动。
本层到下一层的操作，添加一个路径上的元素。
回调函数。
下一层回本层的操作，pop刚才添加的路径上的元素。
完整代码
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = []
path = []
def backtrack(startindex):
# 确定终止条件
res.append(path[:])
for i in range(startindex,len(nums)):
path.append(nums[i])
backtrack(i+1)
path.pop()
backtrack(0)
return res