【回溯算法】——78.子集

78. 子集

一、题目难度

中等

二、相关标签与相关企业

[相关标签]
[相关企业]

三、题目描述

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

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

四、示例

示例1

输入：nums = [1, 2, 3]
输出：[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

示例2

输入：nums = [0]
输出：[[], [0]]

五、提示

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

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        # 1.定义回溯函数的参数
        result = []                 # 存储结果
        path = []                   # 记录每一种子集情况
        used = [False] * len(nums)  # 标记元素使用情况

        # 2.设置回溯终止条件：
        def backtracking(nums, path, startIndex, result):
            """
            回溯函数:
            :param nums:
            :param path:
            :param startIndex:从该位置开始选择元素添加进子集，用于避免生成重复子集
            :param result: 用于存储最终所有自己结果
            """
            # 进入这一层后，
            result.append(path.copy())

            # 循环遍历数组nums，从startIndex位置开始
            for i in range(startIndex, len(nums)):
                # 将当前元素nums[i]添加到path中，表示该元素作为子集一部分
                path.append(nums[i])

                # 添加后，相当于完成一层搜索，
                # 调用自身，进行递归，进入下一层 i+1 搜索
                backtracking(nums, path, i + 1, result)

                # 递归调用返回后（完成下一层搜索），进行回溯
                # 将path最后一个元素弹出，恢复到添加该元素之前的状态
                # 以便尝试下一个
                path.pop()
        backtracking(nums, [], 0, result)
        return result