Buckle 78: subset

Power button 78： A subset of

Title Description

Give you an array of integers nums , Elements in an array Different from each other . Returns all possible subsets of the array （ Power set ）.

Solution set You can't Contains a subset of repetitions . You can press In any order Returns the solution set .

I / O example

 Input ：nums = [1,2,3]
 Output ：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

 Input ：nums = [0]
 Output ：[[],[0]]

Algorithm one , Use a dictionary for backtracking

 vector<vector<int>>subsets(vector<int>&nums)
        {
    
            // Set judgment array 
            vector<bool>vaild(nums.size(),false);
            // Set save array 
            vector<vector<int>>res;

            // Set the traversal depth 
            int depth=0;
            // Length of array 
            int length=nums.size();

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

            return res;


        }

        // Establish functions to realize the function of iteration , according to vaild The change of function value is realized 
        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{
    
                // Change the current vaild Two fractions of value true and false, Keep exploring 
                vaild[depth]=true;
                getSubsets(nums,length,depth+1,vaild,res);
                vaild[depth]=false;
                getSubsets(nums,length,depth+1,vaild,res);

            }
            
        }

Algorithm 2 , Using backtracking

  // Use the idea of iteration 
          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();
                }
          }

Algorithm 3： Use dynamic programming

   // Using the idea of dynamic programming 
        vector<vector<int>>subsets3(vector<int>&nums)
        {
    
            vector<vector<int>>res;
            vector<int>path;
            // Add an empty set to the array first 
            res.push_back(path);

            for(int i=0;i<nums.size();i++)
            {
    
                int size=res.size();
                // Add... To the previous subset 
                for(int j=0;j<size;j++)
                {
    
                    vector<int>newList=res[j];
                    newList.push_back(nums[i]);
                    res.push_back(newList);
                }
            }
            return res;
        }