[leetcode]78#サブセット(subsets)-再帰

Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: nums = [1,2,3] Output: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
分析:本題は八皇后問題と類似しており、再帰的に次の問題にアクセスしている.次の図のように、最後にPythonとC++で実装されたコードです.Python

class Solution(object):
    def subsets(self, nums):
        result=[]
    
        def dfs(lst, nums, pos):    #pos  lst   
            result.append(lst[:]) #     
            
            for i in range(pos,len(nums)):
                lst.append(nums[i])
                dfs(lst,nums,i+1)
                lst.pop() #       
                
        dfs([],nums,0)
        return result

c++メソッド1:

class Solution {
public:    
  //          
   vector<vector<int>> subsets(vector<int>& nums) {
       //     ：      
       vector<vector<int>> result;
       vector<int> path;  
       //     ：  ，       
       sort(nums.begin(),nums.end());
       result.push_back(path);
       dfs(nums,0,path,result);
       return result;
   }
   void dfs(vector<int>& nums,int pos,vector<int> & path,vector<vector<int>> & result)
   //num        
   {
          if(pos==nums.size())
              return;
  //        
  //     ：https://blog.csdn.net/lyly1995/article/details/87867340
          for(int i=pos;i<nums.size();i++)
          {
              path.push_back(nums[i]);
              result.push_back(path);
              dfs(nums,i+1,path,result);
              path.pop_back();
          }
   }

};

c++メソッド2 1は、配列を並べ替えるのではなく、アクセスした要素2を1つの配列で記録し、最後に出力/格納配列を巡回する

class Solution {
public:
 int used[1000000];

  void search(vector<int>& nums,int idx,vector<int> & path,vector<vector<int>> & result)
  {
      if(idx>=nums.size()){
          for(int i=0;i<nums.size();i++)
          {
              if(used[i]==1)
                 path.push_back(nums[i]);
          }
          result.push_back(path);
          path.clear();
          return;
      }
      used[idx]=1;
      search(nums,idx+1,path,result);
      used[idx]=0;
      search(nums,idx+1,path,result);
  }
  vector<vector<int>> subsets(vector<int>& nums) {
      memset(used,0,sizeof(used));
      vector<vector<int>> result;
      vector<int> path;
      search(nums,0,path,result);
      return result;
      }
};