LeetCode 78. 子集

Categories:

Tags:

题目描述
思路分析
1. 解法一：回溯（推荐）
2. 解法二：二进制枚举（位运算）
相似题目

题目描述

✅ 78. 子集

思路分析

解法一：回溯（推荐）

核心思路：

子集问题中每个元素都有”选”或”不选”两种决策，共 2ⁿ 种结果。

每进入递归就先将当前路径 path 加入结果集（空集也是子集）。

从 start 开始枚举，选取 nums[i] 加入 path，递归进入 i+1。

回溯时弹出 path 最后一个元素，尝试下一个选择。

start 保证每次只往后选，避免生成重复子集。

复杂度分析：

时间复杂度：O(n × 2^n)，其中 n 为数组长度，共 2^n 个子集，每个子集平均长度 n/2

空间复杂度：O(n)，其中 n 为数组长度，递归栈最大深度为 n

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), res);
        return res;
    }

    private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
        // 每次进入递归都将当前路径加入结果集（包含空集）
        res.add(new ArrayList<>(path));
        for (int i = start; i < nums.length; i++) {
            // 做选择：将当前元素加入路径
            path.add(nums[i]);
            // 递归：从下一个位置继续选择
            backtrack(nums, i + 1, path, res);
            // 撤销选择：回溯到上一状态
            path.remove(path.size() - 1);
        }
    }
}

func subsets(nums []int) [][]int {
    var res [][]int
    var path []int

    var backtrack func(start int)
    backtrack = func(start int) {
        // 每次进入递归都将当前路径加入结果集（包含空集）
        res = append(res, append([]int{}, path...))

        for i := start; i < len(nums); i++ {
            // 做选择：将当前元素加入路径
            path = append(path, nums[i])
            // 递归：从下一个位置继续选择
            backtrack(i + 1)
            // 撤销选择：回溯到上一状态
            path = path[:len(path)-1]
        }
    }

    backtrack(0)
    return res
}

解法二：二进制枚举（位运算）

核心思路：

用 n 位整数的每一位表示该位置的元素是否被选中：第 i 位为 1 表示选 nums[i]，为 0 表示不选。

枚举 mask 从 0 到 2ⁿ - 1，每个 mask 对应唯一一个子集。

对每个 mask，遍历所有位，检查第 i 位是否为 1，将对应元素加入当前子集。

该方案无需递归，代码简洁，适合 n ≤ 20 的场景（受整数位宽限制）。

复杂度分析：

时间复杂度：O(n × 2^n)，其中 n 为数组长度，共 2^n 个 mask，每个 mask 需要 O(n) 时间处理

空间复杂度：O(n)，其中 n 为数组长度，临时子集数组的最大长度为 n

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        // 枚举所有可能的掩码，共 2^n 个子集
        for (int mask = 0; mask < (1 << n); mask++) {
            List<Integer> subset = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                // 检查第 i 位是否为 1，若是则选取 nums[i]
                if ((mask >> i & 1) == 1) {
                    subset.add(nums[i]);
                }
            }
            res.add(subset);
        }
        return res;
    }
}

func subsets(nums []int) [][]int {
    n := len(nums)
    var res [][]int
    // 枚举所有可能的掩码，共 2^n 个子集
    for mask := 0; mask < (1 << n); mask++ {
        var subset []int
        for i := 0; i < n; i++ {
            // 检查第 i 位是否为 1，若是则选取 nums[i]
            if mask>>i&1 == 1 {
                subset = append(subset, nums[i])
            }
        }
        res = append(res, subset)
    }
    return res
}

相似题目

题目	难度	考察点
90. 子集 II	中等	回溯、去重
46. 全排列	中等	回溯、全排列
47. 全排列 II	中等	回溯、去重
39. 组合总和	中等	回溯、组合
40. 组合总和 II	中等	回溯、去重
77. 组合	中等	回溯、组合
491. 非递减子序列	中等	回溯、子序列

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/26448849