Leetcode78. 子集

题目描述

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

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

示例 1：

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

示例 2：

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

提示：

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

解题思路

这道题只能用暴力枚举的方式求解。使用DFS+回溯实现比较简单。

用index来代表当前处理元素的下标，对于每一个元素，都有选择和不选择两种状态，对这两种情况分别递归：

如果不选择当前元素，则：

1
DFS(nums,index+1,temp);

直接递归下一个元素即可。

如果选择当前元素，则：

1
2
temp.push_back(nums[index]);
DFS(nums,index+1,temp);

将当前元素加入一个可能的答案序列，然后递归处理下一个元素。

最后我们需要一个递归出口：

当数组全部元素都被处理过之后，将一个答案添加到最终的答案数组，如下：

1
2
3
4
5
if(index>=nums.size())
{
ans.push_back(temp);
return;
}

具体细节如示例代码所示。

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<vector<int>>ans;

void DFS(vector<int>& nums,int index,vector<int>temp)
{
    if(index>=nums.size())
    {
        ans.push_back(temp);
        return;
    }
    DFS(nums,index+1,temp);
    temp.push_back(nums[index]);
    DFS(nums,index+1,temp);
}

vector<vector<int>> subsets(vector<int>& nums)
{
    if(nums.empty()) return {{}};
    vector<int>temp;
    DFS(nums,0,temp);
    return ans;
}

时间复杂度为：$$O(n \times 2 ^ n)$$。一共$ 2^n$个状态，每种状态需要 O(n)O(n)的时间来构造子集。

空间复杂度：O(n)O(n)。临时数组temp的空间代价是 O(n)O(n)，递归时栈空间的代价为O(n)O(n)。