Leetcode78. 子集

2021年5月14日 78Browse 1Like 0Comments

题目描述

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

解题思路

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

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

如果不选择当前元素,则:

DFS(nums,index+1,temp);

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

如果选择当前元素,则:

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

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

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

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

if(index>=nums.size())
{
ans.push_back(temp);
return;
}

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

示例代码

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)$。临时数组temp的空间代价是 $O(n)$,递归时栈空间的代价为$O(n)$。

agedcat_xuanzai

这个人很懒,什么都没留下

Comments