题目

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

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

示例 1：

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

示例 2：

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

提示：

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

实现代码

使用DFS实现回溯算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    List<List<Integer>> result = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> subsets(int[] nums) {

        backtrack(nums, 0);
        return result;
    }

    private void backtrack(int[] nums, int start) {

        // 每次都需要新的容器把当前路径复制过去
        result.add(new LinkedList<>(path));

        for (int i = start; i < nums.length; i++) {

            path.addLast(nums[i]);
            backtrack(nums, i + 1);
            path.removeLast();
        }
    }
}

思路讲解

假设数组为[3, 7, 9]，那么所有的子集为[[], [3], [7], [9], [3,7], [3,9], [7,9], [3,7,9]]，构建为一棵树如下：

image-20250926001424739

通过上图可知规律，每往下走一层，其子节点都是当前节点索引值后面的索引值。比如：

  • 第二层索引值0的节点，其子节点就是索引1、2
  • 第三层索引值1的节点，其子节点就是索引2
  • 第二层索引值2的节点，因为数组最大索引值为2，所以后面没有元素，没有子节点

这样设计的目的是避免重复：确保每个子集只会被生成一次，例如[3,7]和[7,3]被认为是同一个子集。

在代码实现时，每个节点进入下一层时将当前索引值加1传递下去，即backtrack(nums, i + 1)。

时间复杂度

假设数组元素数量为n，那么子集的数量就为2^n，再看每个节点的处理情况，tranceList.add(new LinkedList<>(trance));，每次都需要将trance所有的元素复制给一个新链表集合，时间复杂度为n，所以总时间复杂度为O(n*2^n)；

空间复杂度

主要的额外空间消耗来自：

  1. result：存储所有子集，共有2^n个子集，每个子集平均长度为n/2，所以空间复杂度为O(n*2^n)
  2. path：递归过程中存储当前路径，最大深度为n，空间复杂度为O(n)
  3. 递归调用栈：最大深度为n，空间复杂度为O(n)

因此总的空间复杂度为O(n*2^n)