backtracking medium

题目

给定一组不含重复元素的整数数组 nums ，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

  1. 输入: nums = [1,2,3]
  2. 输出:
  3. [
  4.   [3],
  5.   [1],
  6.   [2],
  7.   [1,2,3],
  8.   [1,3],
  9.   [2,3],
  10.   [1,2],
  11.   []
  12. ]

思路

方法一：迭代

开始假设输出子集为空，每一步都向子集添加新的整数，并生成新的子集。
78. 子集 - 图1
代码实现

class Solution:
    def subsets(self, nums):
        result = [[]]

        for num in nums:
            newsets = []
            for subset in result:
                new_subset = subset + [num]
                newsets.append(new_subset)
            result.extend(newsets)
        return result

class Solution:
    def subsets(self, nums):
        res = [[]]

        for num in nums:
            res += [curr + [num] for curr in res]
        return res
# 看看人家语法糖写的， 啊！！！ 看看你自己！！ 什么东西

复杂度分析

  • 时间复杂度：78. 子集 - 图2，生成所有子集，并复制到输出结果中。
  • 空间复杂度：78. 子集 - 图3，这是子集的数量。
    • 对于给定的任意元素，它在子集中有两种情况，存在或者不存在（对应二进制中的 0 和 1）。因此， N 个数字共有 78. 子集 - 图4个子集。

      注意 append() 和 extend() 的用法区别

方法二：回溯

幂集是所有长度从 0 到 n 所有子集的组合。根据定义，该问题可以看作是从序列中生成幂集。遍历 子集长度，通过 回溯 生成所有给定长度的子集。
78. 子集 - 图5

回溯法是一种探索所有潜在可能性找到解决方案的算法。如果当前方案不是正确的解决方案，或者不是最后一个正确的解决方案，则回溯法通过修改上一步的值继续寻找解决方案。

78. 子集 - 图6

算法描述**
定义一个回溯方法 backtrack(first, curr) ，第一个参数为索引 first ，第二个参数为当前子集 curr 。

  • 如果当前子集构造完成，将它添加到输出集合中。
  • 否则，从 first 到 n 遍历索引 i 。
    • 将整数 nums[i] 添加到当前子集 curr 。
    • 继续向子集中添加整数： backtrack(i + 1, curr) 。
    • 从 curr 中删除 nums[i] 进行回溯。

代码实现

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        n = len(nums)

        def helper(i, tmp):
            res.append(tmp)
            for j in range(i, n):
                helper(j + 1, tmp + [nums[j]])
        helper(0, [])
        return res

复杂度分析

  • 时间复杂度：78. 子集 - 图7，生成所有子集，并复制到输出集合中。
  • 空间复杂度：78. 子集 - 图8，存储所有子集，共 n 个元素，每个元素都有可能存在或者不存在。

作者：LeetCode 链接：https://leetcode-cn.com/problems/subsets/solution/zi-ji-by-leetcode/