How do I handle duplicates when solving Subsets II?

Duplicates in Subsets II are managed by sorting the array first, then skipping over duplicate elements during backtracking. This prevents redundant subsets.

What is the best approach for generating subsets without duplicates?

The best approach is to use backtracking with pruning. Sorting the array ensures duplicates are grouped together, and skipping over them during recursion eliminates redundant subsets.

How does backtracking with pruning work in Subsets II?

Backtracking with pruning works by recursively building subsets, and pruning occurs by skipping over duplicate elements to avoid redundant subsets from being added to the result.

Why is sorting the input array important in Subsets II?

Sorting the input array helps group duplicate elements together, making it easier to identify and skip over them during the backtracking process, ensuring unique subsets.

What is the time complexity of the Subsets II problem?

The time complexity of Subsets II is $O(2^n)$, where n is the length of the input array. The pruning technique reduces redundant calculations, but the overall complexity still depends on the number of subsets.

#90

Medium

auto_awesome回溯·pruning

LeetCode 题解工作台

子集 II

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。返回的解集中，子集可以按任意顺序排列。示例 1：输入： nums = [1,2,2] 输出： [[],[1],[1,2],[1,2,2],[2],[2,2]] 示例 2…

数组回溯位运算

题目描述

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

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

示例 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

lightbulb

解题思路

方法一：排序 + DFS

我们可以先对数组 $\textit{nums}$ 进行排序，方便去重。

然后，我们设计一个函数 $\textit{dfs}(i)$ ，表示当前从第 $i$ 个元素开始搜索子集。函数 $\textit{dfs}(i)$ 的执行逻辑如下：

如果 $i \geq n$ ，说明已经搜索完所有元素，将当前子集加入答案数组中，递归结束。

如果 $i < n$ ，将第 $i$ 个元素加入子集，执行 $\textit{dfs}(i + 1)$ ，然后将第 $i$ 个元素从子集中移除。接下来，我们判断第 $i$ 个元素是否和下一个元素相同，如果相同，则循环跳过该元素，直到找到第一个和第 $i$ 个元素不同的元素，执行 $\textit{dfs}(i + 1)$ 。

最后，我们只需要调用 $\textit{dfs}(0)$ ，返回答案数组即可。

时间复杂度 $O(n \times 2^n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组 $\textit{nums}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        def dfs(i: int):
            if i == len(nums):
                ans.append(t[:])
                return
            t.append(nums[i])
            dfs(i + 1)
            x = t.pop()
            while i + 1 < len(nums) and nums[i + 1] == x:
                i += 1
            dfs(i + 1)

        nums.sort()
        ans = []
        t = []
        dfs(0)
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ability to manage duplicate subsets effectively is key to solving this problem.
question_mark
Understanding backtracking with pruning demonstrates good problem-solving skills.
question_mark
Familiarity with subset generation, recursive exploration, and skipping duplicates is crucial.

warning

常见陷阱

外企场景

error
Forgetting to skip duplicate elements leads to redundant subsets being included in the final result.
error
Not sorting the input array can make it difficult to recognize and skip duplicates.
error
Failing to prune the recursive tree efficiently can lead to unnecessary computations.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Handling arrays of varying sizes up to 10 elements with more complex duplicates.
arrow_right_alt
Adapting the approach for larger datasets that might not fit in memory or have different constraints.
arrow_right_alt
Modifying the solution to generate subsets of a specific size or meet additional requirements.

help

常见问题

外企场景

继续练习

#78 子集 #473 火柴拼正方形 #491 非递减子序列