LeetCode 0078. Subsets子集【Python】

LeetCode 0078. Subsets子集【Medium】【Python】【回溯】

Problem

LeetCode

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

问题

力扣

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

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

示例:

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

思路

回溯

也是稍微改造一下 labuladong 的回溯模板就行。

Python3 代码

from typing import List

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

        def backtrack(nums, start, path):
            # 加入 path
            res.append(path)
            # i 从 start 开始递增
            for i in range(start, n):
                # 回溯及更新 path
                # path.append([nums[i]])
                backtrack(nums, i + 1, path + [nums[i]])
                # path.pop()

        backtrack(nums, 0, [])
        return res

有一点疑惑，回溯更新 path 那里使用如下代码就运行不出正确结果，暂时还没找到原因：

for i in range(start, n):
    # 回溯及更新 path
    path.append(nums[i])
    backtrack(nums, i + 1, path)
    path.pop()

GitHub 链接

Python