Leetcode-90-子集 II

# Leetcode-90-子集 II

# 题目说明

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

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

示例 1：

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

1
2

示例 2：

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

1
2

提示：

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

来源：力扣（LeetCode）链接：https://leetcode.cn/problems/subsets-ii

# 题解

# 回溯法

def backtracking(nums, result, length, index, subset):
    if length == len(subset):
        result.append(subset.copy())
        return
    for i in range(index, len(nums)):
        if i > index and nums[i-1]==nums[i]:
            continue
        subset.append(nums[i])
        backtracking(nums, result, length, i+1, subset)
        subset.pop()


def fun(nums):
    result = []
    result.append([])
    nums.sort()
    for i in range(1, len(nums) + 1):
        backtracking(nums, result, i, 0, [])
    return result

print(fun([1,2,2]))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

执行结果:

[[], [1], [2], [1, 2], [2, 2], [1, 2, 2]]

# DFS

def dfs(nums, result, index, subset):
    result.append(subset.copy())
    for i in range(index, len(nums)):
        if i > index and nums[i-1]==nums[i]:
            continue
        subset.append(nums[i])
        dfs(nums, result, i+1, subset)
        subset.pop()

def fun(nums):
    nums.sort()
    result = []
    dfs(nums, result, 0, [])
    return result

print(fun([1,2,2]))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

执行结果：

[[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]

编辑

#回溯法 #DFS

上次更新: 2023/02/16, 22:15:06

← Leetcode-78-子集 Linux内核模块→