力扣剑指 Offer II 079. 所有子集

最新推荐文章于 2025-05-29 23:21:11 发布

三更鬼

最新推荐文章于 2025-05-29 23:21:11 发布

阅读量123

点赞数

分类专栏： DFS 文章标签： leetcode 深度优先算法

本文链接：https://blog.csdn.net/csdn_muxin/article/details/125015209

版权

DFS 专栏收录该内容

28 篇文章

订阅专栏

该篇博客介绍了一种解决数组子集问题的方法，利用深度优先搜索（DFS）和回溯策略。题目要求在长度不超过10的无重复元素数组中找出所有可能的子集。代码中定义了一个`Solution`类，包含一个`ans`列表存储子集结果，通过`dfs`方法递归地生成所有子集。在`dfs`过程中，当遍历完数组时，将当前子集添加到答案中，遍历过程中可以选择添加或跳过当前元素，并在回溯时从列表中移除当前元素。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目来源：https://leetcode.cn/problems/TVdhkn/

大致题意：
给一个不含重复元素的数组（长度不大于 10），求出数组的所有子集

思路

题目中限制了数组长度，于是可以使用 dfs + 回溯的思路枚举出所有子集

DFS + 回溯

从第一个元素出发，使用 list 存下当前子集
每次遍历到一个元素时，可以选择跳过当前元素，直接调用 dfs 遍历下一个位置；也可以选择添加当前元素到 list，再调用 dfs 遍历下一个位置（此时在跳出 dfs 后，需要回溯，将当前元素从 list 中取出）
若数组已经遍历完，则将当前 list 代表的子集放入答案中

代码：

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

    public void dfs(int[] nums, int i, List<Integer> list) {
        // 数据遍历完，将当前 list 内容表示的子集加入答案
        if (i == nums.length) {
            ans.add(new ArrayList<>(list));
            return;
        }
        // 跳过当前元素
        dfs(nums, i + 1, list);
		// 添加当前元素
        list.add(nums[i]);
        dfs(nums, i + 1, list);
        // 回溯，取出当前元素
        list.remove(list.size() - 1);
    }
}