算法学习

Appearance

78. 子集 Medium ​

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

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

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

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

解题思路 ​

输入：给定一个不包含重复元素的整数数组 nums

输出：返回数组所有可能的子集

这道题是典型的子集型回溯问题。核心思想是使用回溯算法，探索所有元素的“选”和“不选”两种情况。

回溯三问 ​

  1. 当前操作？

    • 在当前位置 i，尝试选择当前数字 nums[j]（j ∈ [i, n)）加入到当前子集 path 中。
    • 也就是把数字 nums[j] 放到路径里，表示“我选择了这个数字”。

  2. 子问题？

    • 选择了 nums[j] 之后，需要继续递归处理剩余的数字。
    • 也就是从 j+1 位置开始，继续向后挑选数字，保证不重复选择（每个数字只能选一次）。

  3. 下一个子问题？

    • 下一步递归就是 dfs(j+1)，表示从下一个位置开始继续向后选择数字，直到遍历完整个数组。

剪枝条件 ​

  • 这道题本身没有显式的剪枝，每次都可以选择当前数字或不选，但这里使用了 从左到右递归 的方式，避免了重复子集（保证顺序）。

代码实现 ​

方法一：选/不选（递归二叉树） ​

对于每个元素，有“选”和“不选”两种可能，就像一棵二叉树的左右分支。

  1. 不选当前元素 直接进入 dfs(i + 1)，递归到下一个元素。

  2. 选当前元素

    • 将当前元素添加到 path 中。
    • 继续进入 dfs(i + 1)，递归到下一个元素。
    • 回溯（撤销选择）时执行 path.pop()，把当前元素移除，防止影响到其他分支。

  3. 递归结束条件 当下标 i 超过数组长度时，将当前的 path 复制到 ans 中，完成一次完整子集的保存。

这种方式的特点是：只有在叶子节点（遍历到数组末尾）才收集结果。

python
from typing import List

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []  # 用于保存所有子集
        path = []  # 当前构造的子集
        n = len(nums)  # 数组长度

        def dfs(i):
            """
            深度优先搜索，生成子集
            i: 当前考虑的元素下标
            """
            # 如果所有数字都考虑完了，就把当前子集path加入答案
            if i >= n:
                ans.append(path.copy())  # 这里必须用copy()避免引用问题
                return

            # 不选择当前元素，直接跳到下一个元素
            dfs(i + 1)

            # 选择当前元素
            path.append(nums[i])
            dfs(i + 1)  # 继续递归到下一个元素

            # 回溯，撤销选择
            path.pop()

        # 从第0个元素开始递归
        dfs(0)
        return ans
javascript
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
const subsets = function(nums) {
    const ans = [];
    const path = [];
    
    function dfs(i) {
        if (i >= nums.length) {
            ans.push([...path]);
            return;
        }

        dfs(i + 1);

        path.push(nums[i]);
        dfs(i + 1);
        path.pop();
    }

    dfs(0);
    return ans;
};

方法二：每次遍历都收集结果 ​

我们可以在递归的每一层都把当前的 path 直接加入到结果中，因为后续可以全部都不选。

  1. 每次递归都记录结果 因为每一条路径都对应一个子集，所以每次进入递归就把当前的 path 加入到 ans。

  2. 遍历所有分支 使用一个循环，从当前下标 i 到数组末尾，尝试选择每一个元素。

    • 选择当前元素 nums[j]，添加到 path。
    • 递归进入下一层 dfs(j + 1)。
    • 回溯（撤销选择）时执行 path.pop()。

  3. 递归结束条件 当下标超过数组长度时，函数自然返回。

这种方式的特点是：每层递归都收集结果，而且通过 for 循环来避免重复。

python
from typing import List

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []  # 用于保存所有子集
        path = []  # 当前构造的子集
        n = len(nums)  # 数组长度

        def dfs(index: int):
            """
            index: 当前考虑的元素下标
            """
            # 直接把当前路径加入答案，因为每一步都可能是一个子集
            ans.append(path.copy())

            # 从当前下标开始，依次尝试加入后续元素
            for i in range(index, n):
                # 选择当前元素
                path.append(nums[i])
                # 递归进入下一层
                dfs(i + 1)
                # 撤销选择，回溯
                path.pop()

        dfs(0)
        return ans
javascript
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
const subsets = function(nums) {
    const ans = [];
    const path = [];
    
    function dfs(i) {
        ans.push([...path]);
        if (i >= nums.length) return;

        for (let j = i; j < nums.length; j++) {
            path.push(nums[j]);
            dfs(j + 1);
            path.pop();
        }
    }

    dfs(0);
    return ans;
};

复杂度分析 ​

时间复杂度：O(n * 2^n)

空间复杂度：O(n * 2^n)

链接 ​

78 国际版

78 中文版