leetcode(力扣) 78. 子集（回溯 & 巧妙解法）

文章目录

• ​​题目描述​​
• ​​法一(巧妙暴力解)​​

• ​​思路分析​​
• ​​完整代码​​

• ​​法二(回溯):​​

• ​​思路分析​​
• ​​完整代码​​

题目描述

给你一个整数数组 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循环完成就行了。

完整代码

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