力扣78：子集

力扣78：子集

题目描述

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

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

输入输出示例

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

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

算法一，使用字典进行回溯

 vector<vector<int>>subsets(vector<int>&nums)
        {
    
            //设定判断数组
            vector<bool>vaild(nums.size(),false);
            //设定保存数组
            vector<vector<int>>res;

            //设置遍历的深度
            int depth=0;
            //数组的长度
            int length=nums.size();

            getSubsets(nums,length,depth,vaild,res);

            return res;


        }

        //建立函数实现迭代的功能,根据vaild函数值的变化实现
        void getSubsets(vector<int>nums,int length,int depth,vector<bool>&vaild,vector<vector<int>>&res)
        {
       
            vector<int>path;
            if(depth==length)
            {
    
                for(int i=0;i<length;i++)
                {
    
                    if(vaild[i]==true)
                    {
    
                        path.push_back(nums[i]);
                    }
                }
                res.push_back(path);
            }
            else{
    
                //将当前的vaild值的两个分成true和false，不断进行下探
                vaild[depth]=true;
                getSubsets(nums,length,depth+1,vaild,res);
                vaild[depth]=false;
                getSubsets(nums,length,depth+1,vaild,res);

            }
            
        }

算法二，使用回溯

  //使用迭代的思想
          vector<vector<int>>subsets2(vector<int>&nums)
          {
    
            vector<vector<int>>res;
            vector<int>path;
            int start=0;
            backTrack(nums,path,start,res);
            return res;
          }

          void backTrack(vector<int>nums,vector<int>&path,int start,vector<vector<int>>&res)
          {
    
                res.push_back(path);
                for(int i=start;i<nums.size();i++)
                {
    
                    path.push_back(nums[i]);
                    backTrack(nums,path,i+1,res);
                    path.pop_back();
                }
          }

算法3：使用动态规划

   //使用动态规划的思想
        vector<vector<int>>subsets3(vector<int>&nums)
        {
    
            vector<vector<int>>res;
            vector<int>path;
            //将空集先加入到数组中
            res.push_back(path);

            for(int i=0;i<nums.size();i++)
            {
    
                int size=res.size();
                //往上一个子集中添加
                for(int j=0;j<size;j++)
                {
    
                    vector<int>newList=res[j];
                    newList.push_back(nums[i]);
                    res.push_back(newList);
                }
            }
            return res;
        }