题解 | #集合的所有子集(二)#

题目分析

1. 题目给出了我们一个一维数组
2. 题目要求我们返回一个二维数组，其中每一个元素是一维数组的子集集合，并且要求此数组按字典序排序

方法一：递归未剪枝

• 实现思路
  • 我们规定一个递归函数，其功能是
    • 对于起点start元素，考虑在当前的path基础上，通过for循环将从start开始到数组末尾的所有元素都尝试在path上添加一次，这样操作保证了字典序
    • 每一轮循环内都进行下一次递归，保证按照深度优先构造path
  • 还需要注意的是，递归函数首先要检查path是否已经在res中出现过，因为如果给定的nums数组中包含重复数字的话，子集不能多次利用相同的数字的

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型二维数组
#
class Solution:
    def subsets(self , nums: List[int]) -> List[List[int]]:
        # write code here
        res=[]
        nums.sort()
        def backtrace(start,path):
            if path not in res:                     # 如果出现重复的结果则不加入res中
                res.append(path)                    
            for i in range(start,len(nums)):        # 定一个起点开始深度递归
                cur_path=path+[nums[i]]
                backtrace(1+i, cur_path)
        backtrace(0,[])
        return res

复杂度分析

• 时间复杂度：$O(n\times 2^n)O(n\times 2^n)$，一共$2^{n}2^n$个状态，每个状态需要$O(n)O(n)$的时间代价来构造
• 空间复杂度：$O(n)O(n)$，递归深度的空间开销

方法二：递归剪枝

• 实现思路

  • 相比于方法一，我们引入了add集合

  • 该集合相当于对nums中的元素进行了去重操作，因此相当于数组的长度$nn$的值有一定程度变小，优化了时间开销

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型二维数组
#
class Solution:
    def subsets(self , nums: List[int]) -> List[List[int]]:
        # write code here
        res=[]
        nums.sort()
        def backtrace(start,path):
            res.append(path)                    # 结果加入res中
            add=set()
            for i in range(start,len(nums)):    # 起点
                if nums[i] not in add:          # 判断是否已经存在，元素去重
                    add.add(nums[i])
                    cur_path=path+[nums[i]]
                    backtrace(1+i, cur_path)
        backtrace(0,[])
        return res

复杂度分析

• 时间复杂度：$O(n\times 2^n)O(n\times 2^n)$，一共$2^{n}2^n$个状态，每个状态需要$O(n)O(n)$的时间代价来构造
• 空间复杂度：$O(n)O(n)$，递归深度的空间开销