すべてのサブセットを生成する3つの方法

問題の定義
集合{a 1,a 2,...,an}を与え,集合のすべてのサブセットを出力することを要求する.
例:{1,2}のすべてのサブセットは次のとおりです.
{}
               {1}
               {2}
              {1, 2}
ソリューション
ここでは、古典的な3つの比較的古典的なすべてのサブセットを求める方法を紹介します.その中には再帰的なものもあれば非再帰的なものもあります.詳細は分析を参照してください.(ネット上の関連資料の思想を参考にして、ここでそれらの共有Leetcode:Subsetsが配列のすべてのサブセットを求めることに感謝します)
方法(1)ビット演算に基づく非再帰方法
アイデア:
与えられたセットのサブセットは、各要素が存在するか、存在しないかの組合せ状態で表すことができる.ビット演算に基づいて0~2^nの値をとり,各値のnビットのバイナリ形式はサブセットを表す.
*例:n=5の場合、0の5ビットのバイナリ形式00000は空のセットを表す.
利点:分かりやすく、操作しやすく、効率的です.
欠点:整形のビット数に制限(int 32ビット,long 64)があり,集合を解くことができる大きさを制限しているため,限界がある.

/**
*@brief:      -           
*
*@idea:                            。
*               0~2^n,      n             。
*        ：   n=5,    0 5       00000     。
*@note:       ，           （int 32 ， long 64),             。
*
*
**/

#include
using namespace std;

/////////////////////////////////

/**
*@brief: print all subsets of the given set
*
*@param arr: the given set
*@param n: the size of the given set
*/
void Subsets(int arr[], int n)
{
    for (long i=0; i0)
        {
            if (j&1)
            {
                cout<>1;//    
            ++idx;
        }

        if (i != 0) cout<

方法(2)同質に基づく再帰方法
思想:Subsets({a 1,.,an})=Subsets({a 1,...,an-1})+{an}.Subsets({a1, ..., an-1})
利点:分かりやすく、操作しやすく、解くことができる集合の大きさに制限はありません.
欠点:再帰的な使用、メモリ、効率の面で考慮する必要があります.

/**
*@brief:      -         
*
*@idea: Subsets({a1, .., an}) = Subsets({a1, ..., an-1}) + {an}.Subsets({a1, ..., an-1})
*
*@note:               
**/

#include
#include
using namespace std;

typedef vector Subset;

//////////////////////////////////////

/**
*@brief: get all subsets of the given set
*
*@param subsets: used to store subsets of the given set
*@param arr: the given set
*@param size: the size of the given set
*@param n: the start index of the sub array
*/
void GetSubsets(vector &subsets, int arr[], int size, int n)
{
    //if the sub array is empty
    //then the only subset is empty set
   if (n == size)
   {
       subsets.push_back(Subset());
   }
   else
   {
       GetSubsets(subsets, arr, size, n+1);

       int num = subsets.size();//the number number of subsets

       for (int i=0; i subsets;

    GetSubsets(subsets, arr, 5, 0);

    for (int i=0; i

方法(3)深さ優先探索に基づく完全二叉木の再帰方法
思想:集合のサブセットは、各要素が存在するか、存在しないかの組合せ状態で表すことができる.完全二叉木で表すことができ、完全二叉木の各葉ノードはサブセットを表す.i番目のレイヤの各ノードの左サブツリーはi番目の要素を追加しないことを示し、右サブツリーはi番目の要素を追加することを示す.私たちがしなければならないのはDFSという木です.もちろん明示的な構造は必要ありません.暗黙的な構造でいいです.
利点:分かりやすく、冗長な操作で、集合サイズに制限がないことを解くことができます.
欠点:消費時間とメモリ消費量を再帰的に比較します.

/**
*@brief:      -  DFS   
*
*@idea:                            。
*        *               ，                    。
*          i                i   ，        i   。
*                 DFS   ，         ，      。
*
*@compexity: O(n*2^n)
**/

#include
#include
using namespace std;


///////////////////////////////////////////////////

/**
*@brief: print all subsets of the given set
*
*@param subset: vector to store the current subset's elements
*@param arr: the given set
*@param n: the total size of the given set
*@param index: the current index of the element that the subset will handled
*/
void Subsets(vector &subset, int arr[], int n, int index)
{
    if (index < n)
    {
        //if the subset does not contain the (i+1) th element
        Subsets(subset, arr, n, index+1);

        //if the subset contains the (i+1) th elements
        subset.push_back(arr[index]);
        Subsets(subset, arr, n, index+1);
        subset.pop_back();
    }
    else
    {
        //if the current subset has handle all elements
        //then print the subset
        cout< temp;

    Subsets(temp, arr, 5, 0);

    return 0;
}