What is the key approach for solving the Subsets problem?

The key approach is backtracking with pruning, ensuring that we efficiently explore each subset without duplicating solutions.

How do you avoid duplicate subsets in the Subsets problem?

By pruning unnecessary recursive calls and ensuring that each subset is generated uniquely in the search space.

Can bit manipulation be used for the Subsets problem?

Yes, bit manipulation can represent each subset as a binary number, efficiently generating subsets without recursion.

What is the time complexity of the Subsets problem?

The time complexity is O(N × 2^N), where N is the length of the input array, because there are 2^N subsets.

How can backtracking with pruning optimize the Subsets solution?

Pruning helps avoid redundant calculations by ensuring subsets are generated without revisiting previously explored solutions.

#78

Medium

auto_awesome回溯·pruning

LeetCode 题解工作台

子集

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

数组回溯位运算

题目描述

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

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

示例 1：

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

示例 2：

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

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同

lightbulb

解题思路

方法一：DFS(回溯)

我们设计一个函数 $dfs(i)$ ，表示从数组的第 $i$ 个元素开始搜索所有子集。函数 $dfs(i)$ 的执行逻辑如下：

如果 $i=n$ ，表示当前已经搜索结束，将当前得到的子集 $t$ 加入答案数组 $ans$ 中，然后返回；
否则，我们可以选择不选择当前元素，直接执行 $dfs(i+1)$ ；也可以选择当前元素，即把当前元素 $nums[i]$ 加入子集 $t$ ，然后执行 $dfs(i+1)$ ，注意要在执行 $dfs(i+1)$ 以后再将 $nums[i]$ 从子集 $t$ 中移除（回溯）。

在主函数中，我们调用 $dfs(0)$ ，即从数组的第一个元素开始搜索所有子集。最后返回答案数组 $ans$ 即可。

时间复杂度 $O(n\times 2^n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组的长度。一共有 $2^n$ 个子集，每个子集需要 $O(n)$ 的时间来构造。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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

        ans = []
        t = []
        dfs(0)
        return ans

speed

复杂度分析

指标	值
时间	\mathcal{O}(N \times 2^N)
空间	\mathcal{O}(N)

psychology

面试官常问的追问

外企场景

question_mark
Candidate demonstrates familiarity with backtracking techniques and pruning strategies.
question_mark
Candidate handles edge cases such as small arrays or empty sets.
question_mark
Candidate optimizes the solution and considers different approaches like bit manipulation or iterative methods.

warning

常见陷阱

外企场景

error
Failing to prune unnecessary recursive calls, leading to duplicate subsets.
error
Incorrectly handling the base case or recursion termination, which can result in incomplete subsets.
error
Overcomplicating the problem by not leveraging simpler iterative or bit manipulation techniques.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allow subsets to include duplicate elements.
arrow_right_alt
Return the subsets sorted or in a specific order.
arrow_right_alt
Implement a solution using dynamic programming or memoization.

help

常见问题

外企场景

继续练习

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