【力扣刷题实战】子集

大家好，我是小卡皮巴拉

文章目录

力扣题目：子集

题目描述

解题思路

问题理解

算法选择

具体思路

解题要点

完整代码（C++）

兄弟们共勉！！！

每篇前言

博客主页：小卡皮巴拉

咱的口号：🌹小比特，大梦想🌹

作者请求：由于博主水平有限，难免会有错误和不准之处，我也非常渴望知道这些错误，恳请大佬们批评斧正。

力扣题目：子集

原题链接：78. 子集 - 力扣（LeetCode）

题目描述

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

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

示例 1：

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

示例 2：

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

解题思路

问题理解

本题给定一个元素互不相同的整数数组 nums，要求找出该数组所有可能的子集（幂集），并且解集不能包含重复的子集，最后按任意顺序返回所有子集。

算法选择

采用深度优先搜索（DFS）算法结合回溯思想。通过深度优先搜索遍历所有可能的子集组合，在遍历过程中利用回溯来撤销已经做出的选择，从而尝试其他可能的子集，最终得到所有的子集。

具体思路

初始化：定义一个二维向量 ret 用于存储所有的子集，一个一维向量 path 用于存储当前正在构建的一个子集。
深度优先搜索：调用 dfs 函数开始深度优先搜索，传入数组 nums 和起始索引 0。
- 处理当前子集：每次进入 dfs 函数，首先将当前的 path 加入到 ret 中。这是因为无论当前 path 中包含哪些元素，它都可以作为一个子集存在（包括空集这种情况）。
- 遍历选择：从给定的索引 pos 开始遍历数组 nums。对于每个元素 nums[i]：
  - 将 nums[i] 添加到 path 中，表示选择了该元素用于当前的子集构建。
  - 递归调用 dfs 函数，传入数组 nums 和下一个索引 i + 1，继续构建下一个元素的子集。
- 回溯操作：递归调用返回后，说明当前分支的子集已经构建完毕或者尝试失败，需要回溯。将 path 中最后一个元素移除（即 path.pop_back()），恢复到添加该元素之前的状态，以便尝试其他可能的子集组合。
返回结果：当所有可能的子集都被尝试完毕后，ret 中存储了数组 nums 的所有子集，返回 ret。

解题要点

深度优先搜索的实现：正确实现深度优先搜索算法，通过递归调用逐步构建子集，确保能够遍历到所有可能的子集组合。
回溯的运用：理解回溯的过程，在递归调用返回后，准确地撤销已经做出的选择（如移除 path 中的元素），以便尝试其他可能的子集。
子集的记录：每次进入 dfs 函数时，及时将当前的 path 加入到结果集 ret 中，以保证所有可能的子集都能被记录下来，包括空集这种特殊情况。

完整代码（C++）

class Solution {// 用于存储所有子集（幂集）的二维向量vector<vector<int>> ret;// 用于存储当前正在构建的一个子集的一维向量vector<int> path;
public:vector<vector<int>> subsets(vector<int>& nums) {// 调用深度优先搜索函数 dfs 开始生成子集，从索引 0 开始dfs(nums, 0);// 返回存储所有子集的向量 retreturn ret;}void dfs(vector<int>& nums, int pos){// 将当前正在构建的子集 path 加入到结果向量 ret 中// 无论当前 path 是什么状态，都可以作为一个子集加入结果集，因为空集也是子集ret.push_back(path);// 从索引 pos 开始遍历数组 numsfor (int i = pos; i < nums.size(); i++){// 将当前元素 nums[i] 加入到当前正在构建的子集 path 中path.push_back(nums[i]);// 递归调用 dfs，从下一个位置 i + 1 继续构建子集dfs(nums, i + 1);// 回溯：将当前元素从子集 path 中移除，恢复到添加该元素之前的状态// 以便尝试其他可能的子集组合path.pop_back();}}
};