大家好，我就是那个在B站讲算法的「华南溜达虎」。
找工作gap时间过长和年龄偏大在hr眼中都是减分项，但是在有些人眼中没有生活的工作比gap更可怕。今天看到一位同学gap了半年，刚入职理想汽车1个月就选择了离职，他认为人生辽阔，生活需要工作，但生活不能只有工作。如今新能源车企竞争激烈，工作强度可想而知。
评论区不少人认为楼主以后会后悔的，不过也有很多跟楼主一样追求工作生活平衡的人支持他的选择。不管怎样，每个人的选择都是值得被尊重的。
25届秋招已经开始了，我组织了一个秋招群，大家可以交流学习心得、面试经验，分享工作机会，有啥问题也可以在群里咨询。在群里我整理了一百多家已经启动秋招企业的文档，以及投递入口，每天都会更新，大家只要按照这个文档海投就可以了。
大家互帮互助相信一定可以拿下秋招！计算机相关专业的同学可以 点击底部的「阅读原文」 加群。
言归正传，今天我们来分享一道高频面试题「子集」。
题目描述
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
举个例子：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
思路解析
以nums = [1,2,3]为例，对于数组中的每一个元素，我们都可以选择放入子集，也可以选择不放入子集，我们可以得到一个决策树，如下图。决策树中边上的数字代表做出的选择，边上的[ ]表示没有做选择。决策树的叶子节点表示所有可能的子集。
这个问题是一个标准的回溯问题，通过穷举所有可能的解来寻找满足条件解。采用深度优先搜索，从解空间的一个起始节点出发，沿着一条路径搜索解空间，如果当前路径不可能找到满足条件的解或者当前路径已经是一个满足条件的解时，就回溯到上一个节点，尝试其他的路径。重复这个过程，直到找到所有可能的解，或者解空间被完全搜索。
下面我们给出c++和python的两种代码实现。
c++代码
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> res;
vector<int> tmp;
dfs(nums, 0, tmp, res);
return res;
}
void dfs(vector<int>& nums, int index, vector<int>& tmp, vector<vector<int>>& res) {
//边界条件，index == nums.size()表示搜索完了一条路径
if (index == nums.size()) {
res.push_back(tmp);
return;
}
//tmp中包含nums[index]
tmp.push_back(nums[index]);
dfs(nums, index + 1, tmp, res);
tmp.pop_back();
//tmp中不包含nums[index]
dfs(nums, index + 1, tmp, res);
}
};
python代码
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = []
tmp = []
self.dfs(nums, 0, tmp, res)
return res
def dfs(self, nums, index, tmp, res):
# 边界条件，index == len(nums)表示搜索完了一条路径
if index == len(nums):
res.append(tmp[:])
return
# tmp中包含nums[index]
tmp.append(nums[index])
self.dfs(nums, index + 1, tmp, res)
tmp.pop()
# tmp中不包含nums[index]
self.dfs(nums, index + 1, tmp, res)
复杂度分析
时间复杂度： 总共有2^n个子集，寻找每个子集的时间复杂度为O(n)，所以总的时间复杂度为O(n·2^n)。
空间复杂度： 寻找子集的过程需要用到递归，递归会涉及到函数栈，这里递归的深度为n，加上递归过程中临时数组的使用，总的空间复杂度为O(n)。
号外
经常使用leetcode会员的同学可以使用我的优惠通道啦！
https://leetcode.cn/premium/?promoChannel=ldtiger ，年度会员有效期比官网多俩月，季度会员有效期比官网多两个星期，还有专属福利，需要的读者朋友可以找我了解。
今天的分享就到这里，希望大家能有所收获！
