LeetCode 补充题 205. 数组的全部子集

2026-09-14 HGNULB 约 4 分钟

文章信息 2 个分类 3 个标签

分类

补充题中等

题目描述

:::fold-green 相关原题

LeetCode 原题： ✅ 78. 子集

LeetCode 原题枚举互异元素的全部子集；本文额外要求每个子集内部非降序，并约定空输入返回 []。原题限制输入非空。

:::

给定互不相同的整数数组 nums，返回全部子集，要求每个子集内部非降序排列；子集之间顺序不限。按本文约定，空输入返回空结果 []；非空输入的结果包含空子集。

示例 1：

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

示例 2：

输入： nums = []
输出： []
解释： 空输入按本文约定返回空结果。

提示：

0 <= nums.length <= 20
不修改传入的数组。

题意分析

子集内部要求有序，但不能修改原数组，所以先排序副本。元素互不相同，每个子集可以唯一表示为一组递增下标，回溯只沿后续下标扩展即可避免重复生成。

解法：排序 + 回溯

核心思路

[!blue]

空输入先按题面约定返回空结果。非空输入复制后排序，定义 start 为下一次允许选择的最小下标，path 保存当前已经选中的元素。进入一次递归就保存当前路径，因为任意长度的路径都是合法子集，包括根调用的空路径。

枚举 i 从 start 到末尾，加入 nums[i] 后递归到 i+1，返回时删除刚加入的元素。下标严格递增，所以一个元素不会重复使用，路径值也自然非降序；每个子集只有一种递增下标序列，因此既不重复也不遗漏。

保存结果时必须复制 path。回溯会继续修改工作路径，直接保存引用会让之前的结果随之变化。

解题步骤

空输入直接返回空结果，否则复制数组并排序。

进入递归后先保存当前路径副本。

从 start 开始枚举候选，加入后以 i+1 递归，返回时撤销加入。

从 start=0 的空路径开始搜索并返回全部结果。

代码实现

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        if (nums.length == 0) {
            return new ArrayList<>();
        }

        nums = nums.clone();
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();

        backtrack(nums, 0, new ArrayList<>(), ans);

        return ans;
    }

    private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> ans) {
        ans.add(new ArrayList<>(path));

        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            backtrack(nums, i + 1, path, ans);
            path.remove(path.size() - 1);
        }
    }
}

import "sort"

func subsets(nums []int) [][]int {
    if len(nums) == 0 {
        return [][]int{}
    }

    nums = append([]int(nil), nums...)
    sort.Ints(nums)
    ans := make([][]int, 0)
    path := make([]int, 0)

    var backtrack func(int)
    backtrack = func(start int) {
        ans = append(ans, append([]int(nil), path...))

        for i := start; i < len(nums); i++ {
            path = append(path, nums[i])
            backtrack(i + 1)
            path = path[:len(path)-1]
        }
    }

    backtrack(0)
    return ans
}

复杂度分析

时间复杂度：$O(n2^n)$。

空间复杂度：辅助空间 $O(n)$，输出空间 $O(n2^n)$。

关键点总结

[!green]

排序输入副本，回溯时只选择后续下标；每层保存当前路径副本，因此每个子集内部自然有序。

易错点总结

[!yellow]

空输入按题面返回 []；非空输入的根路径才用于生成空子集。

递归到 i+1，不能仍从当前 i 开始，否则会重复使用元素。

排序操作针对副本，结果也保存路径副本；这两处复制解决不同的共享问题。

相似题目

题目	难度	关联与区别
78. 子集	中等	互异元素按下标选取的子集枚举过程相同；本题额外要求子集内部非降序、保留输入不变，并约定空输入返回 []。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/481179313083

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！