78 子集

一、题目

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

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

二、题解

方法一：回溯法

思路：使用回溯枚举所有可能的子集。

1. 核心思路

这道题要求返回所有子集。

对于数组中的每一个元素，都有两种选择：

  • 选择这个元素；
  • 不选择这个元素。

回溯的核心思想是：

  • 使用 path 记录当前正在构造的子集；
  • 每进入一层递归，都把当前 path 加入结果集；
  • 然后继续从后面的元素中选择；
  • 选择一个元素后进入下一层递归；
  • 递归结束后撤销选择，回到上一层状态。

因为题目说明数组中的元素互不相同，所以不需要考虑去重问题。

2. 具体步骤

  1. 定义结果集 result，用来存放所有子集。
  2. 定义路径 path，用来存放当前正在构造的子集。
  3. 从下标 0 开始回溯。
  4. 每进入一层递归，都把当前 path 拷贝一份加入 result。
  5. 从 start 位置开始遍历数组。
  6. 选择当前元素 nums[i]。
  7. 递归处理后面的元素，下一层从 i + 1 开始。
  8. 递归结束后，撤销选择。
  9. 最后返回 result。

3. 关键逻辑

// 当前 path 本身就是一个子集
result.add(new ArrayList<>(path));

for (int i = start; i < nums.length; i++) {
    // 选择 nums[i]
    path.add(nums[i]);

    // 继续向后选择
    backtrack(nums, i + 1, path, result);

    // 撤销选择
    path.remove(path.size() - 1);
}

解释：

  • 每一个递归节点都代表一个子集；
  • 所以每次进入递归时，都要把当前 path 加入结果集；
  • i + 1 表示下一层只能选择当前元素后面的元素，不能回头选；
  • path.remove(path.size() - 1) 是回溯操作，用来撤销刚才的选择。

4. 代码

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        // 1. 定义结果集，存放所有子集
        List<List<Integer>> result = new ArrayList<>();

        // 2. 定义路径，存放当前正在构造的子集
        List<Integer> path = new ArrayList<>();

        // 3. 从下标 0 开始回溯
        backtrack(nums, 0, path, result);

        // 4. 返回结果
        return result;
    }

    private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> result) {
        // 当前 path 就是一个子集，需要加入结果集
        // 注意：这里必须拷贝一份，不能直接添加 path
        result.add(new ArrayList<>(path));

        // 从 start 开始，继续选择后面的元素
        for (int i = start; i < nums.length; i++) {
            // 选择当前元素
            path.add(nums[i]);

            // 递归选择下一个位置之后的元素
            backtrack(nums, i + 1, path, result);

            // 撤销选择，恢复现场
            path.remove(path.size() - 1);
        }
    }
}

5. 复杂度分析

时间复杂度：O(n×2n)O(n \times 2^n)

说明：

数组长度为 n，每个元素都有选和不选两种状态，所以一共有 2^n 个子集。

每次把 path 加入结果集时，需要拷贝当前子集，最多需要 O(n) 时间。

所以总时间复杂度是 O(n×2n)O(n \times 2^n)。

空间复杂度：O(n)O(n)

说明：

递归深度最多为 n，path 中最多存放 n 个元素。

如果不计算返回结果集，空间复杂度是 O(n)O(n)。

如果计算返回结果集，空间复杂度是 O(n×2n)O(n \times 2^n)。

方法二：二进制枚举法

思路：使用二进制状态表示每一个子集。

1. 核心思路

数组中有 n 个元素，每个元素都有两种状态：

  • 0：不选择；
  • 1：选择。

因此可以用一个二进制数来表示一个子集。

例如：

nums = [1,2,3]

可以用三位二进制表示所有子集：

000 -> []
001 -> [1]
010 -> [2]
011 -> [1,2]
100 -> [3]
101 -> [1,3]
110 -> [2,3]
111 -> [1,2,3]

这种方法的核心是：

  • 枚举从 0 到 2^n - 1 的所有数字；
  • 每个数字都代表一个子集；
  • 判断这个数字的每一位是否为 1；
  • 如果某一位是 1，说明选择对应位置的元素。

2. 具体步骤

  1. 定义结果集 result。
  2. 获取数组长度 n。
  3. 子集总数为 1 << n，也就是 2^n。
  4. 枚举每一个状态 mask。
  5. 对于每个 mask，创建一个新的子集 path。
  6. 遍历数组每个下标 i。
  7. 判断 mask 的第 i 位是否为 1。
  8. 如果是 1，就把 nums[i] 加入当前子集。
  9. 将当前子集加入结果集。
  10. 最后返回 result。

3. 关键逻辑

if ((mask & (1 << i)) != 0) {
    path.add(nums[i]);
}

解释：

  • 1 << i 表示只有第 i 位是 1 的二进制数；
  • mask & (1 << i) 用来判断 mask 的第 i 位是不是 1；
  • 如果结果不等于 0，说明第 i 位是 1；
  • 第 i 位是 1，就表示当前子集需要选择 nums[i]。

4. 代码

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        // 1. 定义结果集
        List<List<Integer>> result = new ArrayList<>();

        // 2. 获取数组长度
        int n = nums.length;

        // 3. 子集总数是 2^n
        int total = 1 << n;

        // 4. 枚举所有二进制状态
        for (int mask = 0; mask < total; mask++) {
            // 当前状态对应的子集
            List<Integer> path = new ArrayList<>();

            // 5. 判断每一位是否选择
            for (int i = 0; i < n; i++) {
                // 如果 mask 的第 i 位是 1，说明选择 nums[i]
                if ((mask & (1 << i)) != 0) {
                    path.add(nums[i]);
                }
            }

            // 6. 当前 path 就是一个子集，加入结果集
            result.add(path);
        }

        // 7. 返回结果
        return result;
    }
}

5. 复杂度分析

时间复杂度：O(n×2n)O(n \times 2^n)

说明：

一共有 2^n 个二进制状态。

对于每个状态，都需要遍历数组中的 n 个元素，判断每个元素是否被选择。

所以时间复杂度是 O(n×2n)O(n \times 2^n)。

空间复杂度：O(n)O(n)

说明：

每次构造一个子集时，临时列表 path 最多存放 n 个元素。

如果不计算返回结果集，空间复杂度是 O(n)O(n)。

如果计算返回结果集，空间复杂度是 O(n×2n)O(n \times 2^n)。

评论