Leetcode:Subsetsは配列のすべてのサブセットを求めます

Given a set of distinct integers, S, return all possible subsets.
Note:

Elements in a subset must be in non-descending order.

The solution set must not contain duplicate subsets.

For example, If S =  [1,2,3] , a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

配列のサブセット集合を求める3つの考え方をまとめた.前の2つの考え方はいずれも再帰に基づいているが、出発点は少し異なる.後者の構想はビット演算に基づいているが,元の配列の数には制限がある.
1.DFSベースの再帰
元の配列の各要素は、サブセットに存在するか、存在しないかの2つの状態があります.このようにサブセットを構築する過程で、各要素には2つの選択方法がある:選択、選択しないため、すべての選択状態を表すために1つのツリーを構築することができる:ツリーのi+1層目の0層目のノードなしはサブセットにi番目の要素を追加するか、追加しないかを示し、左サブツリーは追加を示し、右サブツリーは追加しないことを示す.すべてのリーフノードが求められたサブセットです.したがって,DFSの再帰的な考え方を用いてすべてのリーフノードを求めることができる.
コードは次のとおりです.

//S    ，temp     ，level                  ，result       
void subsets(vector &S,vector temp,int level,vector > &result)
    {
        //           result 
        if(level == S.size())
        {
            result.push_back(temp);
            return;
        }
        //       ，         temp 
        subsets(S,temp,level + 1,result);
        //      temp 
        temp.push_back(S[level]);
        subsets(S,temp,level + 1,result);
    }

2.同質に基づく再帰
元の問題より規模が小さいが同質な問題を見つけることができれば,再帰的に解決することができる.例えば{1,2,3}のすべてのサブセットを要求すると,{2,3}のすべてのサブセットを先に求めることができ,{2,3}のサブセットは同時に{1,2,3}のサブセットであり,その後{2,3}のすべてのサブセットに要素1を加えた後(ソートに注意)、同じ数のサブセットも{1,2,3}のサブセットである.これにより,{2,3}のすべてのサブセットを求めることで{1,2,3}のすべてのサブセットを求めることができる.すなわち,1,2,3のサブセットを求めるためには,まず2,3のサブセットを求め,それから1を2,3のサブセットに加える典型的な再帰的な考え方である.コードは次のとおりです.

    vector > subsets(vector &S,int idx,int n)
    {
        vector > result;
        if(idx == n)
        {
            vector temp;
            result.push_back(temp);
        }
        else
        {
            vector > vec = subsets(S,idx + 1,n);
            int a = S[idx];
            for(int i = 0; i < vec.size();i++)
            {
                vector v = vec[i];
                result.push_back(v);
                v.push_back(a);
                sort(v.begin(),v.end());
                result.push_back(v);
            }
        }
        return result;
    }

3.ビット演算
サブセットを求める問題は組合せを求める問題である.配列中のn個の数はn個のバイナリビットで表すことができ,あるビットが1であれば選択対応の数を表し,0であれば選択しない数を表す.

    vector > subsets(vector &S,int n)
    {
       //n   0~max-1 2^n   ，1< >result;
        for(int i = 0;i < max;i++)
        {
            vector temp;
            int idx = 0;
            int j = i;
            while(j > 0)
            {
                //         1，  1             
                if(j&1)
                {
                    temp.push_back(S[idx]);
                }
                idx++;
                //         1    
                j = j>>1;
            }
            //        ，       
            result.push_back(temp);
        }
        return result;
    }