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:

1Input: nums = [1,2,3]
2Output:
3[
4  [3],
5  [1],
6  [2],
7  [1,2,3],
8  [1,3],
9  [2,3],
10  [1,2],
11  []
12]

问题

力扣

给定一组不含重复元素的整数数组 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]

思路

回溯

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

Python3 代码

1from typing import List
2
3class Solution:
4    def subsets(self, nums: List[int]) -> List[List[int]]:
5        res = []
6        n = len(nums)
7
8        def backtrack(nums, start, path):
9            # 加入 path
10            res.append(path)
11            # i 从 start 开始递增
12            for i in range(start, n):
13                # 回溯及更新 path
14                # path.append([nums[i]])
15                backtrack(nums, i + 1, path + [nums[i]])
16                # path.pop()
17        
18        backtrack(nums, 0, [])
19        return res

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

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

GitHub 链接

Python