LeetCode 78. 子集（回溯）

文章目录

• 前言
• 题目
• 题解
• NO1：回溯找节点
• 参考资料

前言

当前为LeetCode 热题 HOT 100专题。

---

题目

题目来源leetcode

leetcode地址：78. 子集，难度：中等。

题目描述(摘自leetcode)：

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

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

示例 2：
输入：nums = [0]
输出：[[],[0]]

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

本地调试代码：

public static void main(String[] args) {
    int[] nums= new int[]{1,2,3};
    System.out.println(new Solution().subsets(nums));
}

---

题解

NO1：回溯找节点

思路：

思路：在递归方法调用过程中使用一个begin来进行直接控制组合，整个结果集添加操作在方法一开始进行，添加新的子集在循环中进行！

代码：

class Solution {
    private List<List<Integer>> res;

    //nums = [1,2,3]  =》 [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
    public List<List<Integer>> subsets(int[] nums) {
        res = new ArrayList<>();
        if (nums.length == 0){
            return res;
        }
        recursion(nums,0, new ArrayList<>());
        return res;
    }

    /**
     * 回溯过程中记录节点
     * @param nums
     * @param begin
     * @param pre
     */
    public void recursion(int nums[],int begin,List<Integer> pre){
        res.add(new ArrayList<>(pre)); /集合的深拷贝
        for (int i = begin; i < nums.length; i++) {  //begin用于间接直接控制组合
            pre.add(nums[i]);
            recursion(nums,i + 1, pre);
            pre.remove(pre.size() - 1);
        }
    }
}

---

参考资料

[1]. leetcode题解

---

我是长路，感谢你的耐心阅读。如有问题请指出，我会积极采纳！ 欢迎关注我的公众号【长路Java】，分享Java学习文章及相关资料 Q群：851968786 我们可以一起探讨学习 注明：转载可，需要附带上文章链接

整理者：长路 时间：2021.12.20