LeetCode 0078. Subsets子集【Medium】【Python】【回溯】
Problem
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()