刷题打卡-子集

程序员小王

发布于 2023-03-21 14:52:59

2020

发布于 2023-03-21 14:52:59

文章被收录于专栏：架构说

一、题目

完成比完美更重要

[78] 子集

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

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

先不要看例子

示例 1：

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

示例 2：

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

二、思路

第一感觉是什么，放弃奇淫技巧。

数学概念子集--->N叉树和栈结构-->递归回溯数--输出路径

从数组到tree思维转换从上到下构造。

图解：

步骤：

复杂度：

时间复杂度：O(n *2 ^ n)

空间复杂度：O(n)

三、代码

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
      
      vector<vector<int>> result;
      vector<int> path;//栈

      dfs(0,nums,path,result);
      return result;
     }

     void dfs(int index, vector<int>& nums,vector<int> &path,vector<vector<int>> &result)
     {  
         if (index > nums.size())
         {
            return ;
         }

         result.push_back(path);

         for (int i = index;i < nums.size();i++ )
         {
            path.push_back(nums[i]);
            dfs(i+1,nums,path,result);
            path.pop_back();
         }
        
     }
};