Leetcode 78. 子集

1.题目描述

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• nums 中的所有元素 互不相同

2.思路分析

如果把 子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！

其实子集也是一种组合问题，因为它的集合是无序的，子集{1,2} 和 子集{2,1}是一样的。

那么既然是无序，取过的元素不会重复取，写回溯算法的时候，for就要从startIndex开始，而不是从0开始！

举个栗子: nums = [1,2,3]为例把求子集抽象为树型结构，如下：

从图中红线部分，可以看出遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合。

回溯三部曲:

回溯函数要处理的参数以及返回值

• 全局变量:result(保存子集集合,二维) path:子集收集元素 startIndex(控制下一层的起始位置)

  result,path = [], []
  def backtrack(nums:List[int], startIndex:int):
  1
  2

递归终止条件:

剩余集合为空时,即为叶子结点。

if (startIndex >= len(nums)):
    return
1
2

其实可以不需要加终止条件，因为startIndex >= nums.size()，本层for循环本来也结束了。

单层搜索逻辑

求取子集问题，不需要任何剪枝！因为子集就是要遍历整棵树。

for i in range(startIndex, len(nums)):
    path.append(nums[i])
    backtrack(nums, i + 1)
    path.pop()
1
2
3
4

3.代码实现

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result, path = [], []

        def backtrack(nums: List[int], startIndex: int) -> None:
            result.append(path[:])
            # 终止条件
            if (startIndex == len(nums)):
                return
            # 单层搜索逻辑
            for i in range(startIndex, len(nums)):
                # 处理节点
                path.append(nums[i])
                # 递归
                backtrack(nums, i+1)
                # 回溯
                path.pop()
        backtrack(nums, 0)
        return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

复杂度分析

• 时间复杂度：(n×2^n)。
• 空间复杂度：O(n)