LeetCode No.90 | StriveZs的博客

LeetCode No.90

LeetCode第九十题—子集II

题目描述

给你一个整数数组 nums ,其中可能包含重复元素,请你返回该数组所有可能的子集(幂集)。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
示例 1

输入:nums = [1,2,2]
输出:[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2

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


提示:

1 <= nums.length <= 10
-10 <= nums[i] <= 10

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution(object):
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]

核心思想:
经典回溯法
def backtrack(path, selected):
if 满足停止条件:
res.append(path)
for 选择 in 选择列表:
做出选择
递归执行backtrack
满足则return True
如果不满足要求就撤销选择
魔改78题就可以了
只需要对生成的结果进行排序,然后判断是否在集合中,如果出现则不行
"""
res = []
res.append([])
numsLen = len(nums)
temp = []

def backtrack(temp, l, numsLen, length):
# 停止条件
if len(temp) == length:
t_1 = sorted(temp)
if t_1 not in res:
tt = copy.copy(t_1)
res.append(tt)
return

for j in range(l + 1, numsLen):
# 做出选择
temp.append(nums[j])
# 递归执行
backtrack(temp, j, numsLen, length)
# 撤销选择
temp.pop()

# 递归调用 length值不同
for i in range(1, numsLen + 1):
backtrack(temp, -1, numsLen, i)
return res
StriveZs wechat
Hobby lead  creation, technology change world.