C++再帰的にサブセットを生成

再帰生成サブセットを利用することは再帰の簡単な応用であり、主な構想はbool配列によって要素が生成されたサブセット内にあるかどうかを識別し、それによってすべてのサブセットを出力することである.次のプログラムはこの機能を実現することができ、空のセットは直接出力されず、要素間はスペースで区切られています.

#include
using std::cout;
using std::cin;
using std::endl;

const int MAX = 10;

template<class T>
void Subset(T list[],bool exists[], int k, int m)
{//list   ，exists           ，k     ，m     
    if(k == m-1) {
        //        ，  exists[i]   0        
        int i = 0;
        exists[k] = 0;
        for(i=0; i1; i++)
            if(exists[i]) cout << list[i] << ' ';
        if(exists[i]) cout << list[i];
        cout << endl;
        exists[k] = 1;
        for(i=0; i1; i++)
            if(exists[i]) cout << list[i] << ' ';
        if(exists[i]) cout << list[i] << endl;
        return;
    }
    exists[k] = 0;//  list[k]     
    Subset(list,exists,k+1,m);
    exists[k] = 1;//  list[k]    
    Subset(list,exists,k+1,m);
}

int main()
{
    char ch[MAX];
    bool exists[MAX] = {0};
    int i = 0;
    while(icin.get(ch[i]);
        if(ch[i] == ' ' || ch[i] == '
')
            break;
        i++;
    }
    Subset(ch,exists,0,i);
}

各要素に2つの値(0,1)を割り当てることで,すべての解の場合を得た.