子集 | LeetCode-78 | 回溯算法

回溯算法练习题 | 子集问题

---

LeetCode链接：78. 子集

---

题目1：78. 子集

1.题目描述

给你一个整数数组 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 中的所有元素 互不相同

2.题解

class Solution {
    // 定义一个列表 result，用于存储最终生成的所有子集
    List<List<Integer>> result = new ArrayList<>();
	// path 用于存储当前路径的子集
    List<Integer> path = new ArrayList<>();
    // 主方法 subsets，输入一个整数数组 nums，返回所有可能的子集
    public List<List<Integer>> subsets(int[] nums) {
        // 调用回溯算法生成所有子集，初始从索引 0 开始
        backtracking(nums, 0);
        // 返回结果列表
        return result;
    }

    // 回溯算法方法 backtracking，构建不同大小的子集
    public void backtracking(int[] nums, int start) {
        // 每次递归调用时，将当前路径 path 的副本加入结果列表中
        result.add(new ArrayList<>(path));

        // 如果 start 已经到达数组末尾，直接返回
        if (start >= nums.length) return;

        // 遍历数组，从 start 开始选择当前元素作为子集的一部分
        for (int i = start; i < nums.length; i++) {
            // 将当前元素加入路径 path
            path.add(nums[i]);
            // 递归调用 backtracking 处理下一个元素，生成包含当前元素的子集
            backtracking(nums, i + 1);
            // 回溯：移除最后加入的元素，尝试其他组合
            path.remove(path.size() - 1);
        }
    }
}

题目2：90. 子集 II

1.题目描述

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 子集（幂集）。

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

示例 1：

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

示例 2：

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

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10

2.题解

class Solution {
    List<List<Integer>> result = new ArrayList<>(); // 存储最终的子集结果
    List<Integer> path = new ArrayList<>(); // 存储当前路径的子集

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums); // 排序以便去重
        backtracking(nums, 0); // 从索引 0 开始回溯
        return result; // 返回所有子集结果
    }

    public void backtracking(int[] nums, int start) {
        result.add(new ArrayList<>(path)); // 将当前路径加入结果列表
        if (start == nums.length) return; // 递归结束条件
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1]) continue; // 跳过重复元素
            path.add(nums[i]); // 将当前元素加入路径
            backtracking(nums, i + 1); // 递归处理下一个元素
            path.remove(path.size() - 1); // 回溯：移除最后添加的元素
        }
    }
}