Leetcode No.78 子集

一、题目描述

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

二、解题思路

这道题告诉我们整数数组 nums 不包含重复元素。因此作图，画出递归树结构是关键。

因为是组合问题，所以我们按顺序读字符，就不需要设置 used 数组；

执行一次深度优先遍历，一条路走到底，当一条路径走完，把路径加入结果集，回溯，继续执行，直到所有路径遍历完毕。

在画树形图的时候，如果新看到的一个数选与不选，可以画出另一棵递归树，这样所有的组合就落在叶子结点处。

三、代码

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> rs;
        vector<int> set;
        int n=nums.size();
        dfs(nums,0,n,set,rs);
        return rs;
    }
    void dfs(vector<int> nums,int index,int n,vector<int> &set,vector<vector<int>> &rs){
        if(index==n){
            rs.push_back(set);
            return;
        }
        set.push_back(nums[index]);
        dfs(nums,index+1,n,set,rs);
        set.pop_back();
        dfs(nums,index+1,n,set,rs);
    }
};

四、复杂度

时间复杂度：O(2^n)，其中n为整数数组 nums的大小。从分析给出的搜索树我们可以看出时间复杂度取决于搜索树所有叶子节点的深度之和，n个位置每次考虑选或者不选，加入答案的时间代价。

空间复杂度：O(n)，其中n为整数数组 nums的大小。除答案数组外，空间复杂度取决于递归的栈深度，在最差情况下需要递归 O(n) 层。平均情况下树的高度与节点数的对数正相关，空间复杂度为 O(logN)。