来源：编程网事
大家好，我就是那个在B站讲算法的「华南溜达虎」。
找工作gap时间过长和年龄偏大在hr眼中都是减分项，但是在有些人眼中没有生活的工作比gap更可怕。今天看到一位同学gap了半年，刚入职理想汽车1个月就选择了离职，他认为人生辽阔，生活需要工作，但生活不能只有工作。如今新能源车企竞争激烈，工作强度可想而知。
评论区不少人认为楼主以后会后悔的，不过也有很多跟楼主一样追求工作生活平衡的人支持他的选择。不管怎样，每个人的选择都是值得被尊重的。
言归正传，今天我们来分享一道高频面试题「子集」。
题目描述
给你一个整数数组 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);
}
};
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)。
特别声明：以上内容仅代表作者本人的观点或立场，不代表新浪财经头条的观点或立场。如因作品内容、版权或其他问题需要与新浪财经头条联系的，请于上述内容发布后的30天内进行。
